?
本节内容的单链表主要以代码及典例题贯彻为主~~如有错误，还请斧正
?
目录
1.单链表的创建
①节点的创建
class ListNode { public int val; public ListNode next;//null public ListNode(int val) { this.val = val; } }②单链表的创建
a.图解?
b.代码
public ListNode head;//链表的头引用 public void createList() { ListNode listNode1 = new ListNode(12); ListNode listNode2 = new ListNode(23); ListNode listNode3 = new ListNode(34); ListNode listNode4 = new ListNode(45); ListNode listNode5 = new ListNode(56); listNode1.next = listNode2; listNode2.next = listNode3; listNode3.next = listNode4; listNode4.next = listNode5; //ListNode5.next = null; this.head = listNode1; }
2.单链表简易操作
①普通的打印
a.定义this.head=cur;
b.当cur!=null时，挨着打印
c.cur=cur.next;
public void display() { //用cur是为了确保head的存在，不然用head的话，遍历完成后将找不到头结点的位置 ListNode cur = head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; }//换行 System.out.println(); }②从指定头节点开始打印
a将指定节点设置为newHead
b.然后就是普通的打印了
public void display2(ListNode newHead) { //用cur是为了确保head的存在，不然用head的话，遍历完成后将找不到头结点的位置 //将指定位置设置为newHead ListNode cur = newHead; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); }③查找是否包含关键字key是否在单链表当中
（实质上就是遍历的思路）
public boolean contains(int key) { ListNode cur=this.head; while(cur!=null){ if(this.cur.val==key){ return true; }cur=cur.next; } return false; }④单链表的长度
（定义一个计数器，每遍历一个count++）
public int size() { int count=0; ListNode cur=this.head; while(cur!=null){ count++; cur=cur.next; } return count; }⑤头插法
a.使该插入节点的指针域指向下一个位置
b.将头节点指向于刚刚插入的结点
代码：
public void addFirst(int data) { //定义这个即将要插入的结点节点 ListNode node=new ListNode(data); node.next=this.head; this.head=node; }?⑥尾插法(注意判断单链表是否为空的情况)
a.遍历到尾节点
b.使尾节点的指针域指向即将插入的节点
?代码：
public void addLast(int data) { ListNode node= new ListNode(data); //当单链表为空时，直接插入该节点 if(this.head==null){ this.node=head; }else{//寻找尾节点 ListNode cur=this.head; while(cur.next!=null){ cur=cur.next; } cur.next=node; } }⑦任意位置插入一个元素,且第一个数据节点为0下标
（插入到某个位置，就要找它前面的那一个位置）
a.不符合条件的情况，index<0或者index>size()
b.当index=0，则就为头插
c.当index=size(),就为尾插
d.其它位置的话，需要先找到其前面那一个位置
public ListNode findIndex(int index) { ListNode cur = this.head; while (index - 1 != 0) { cur = cur.next; index--; } return cur; } //任意位置插入一个元素,且第一个数据节点为0下标 public void addIndex(int index, int data) { if (index < 0 || index > size()) { System.out.println("index位置不合法"); return; } if (index == 0) { addFirst(data); } if (index == size()) { addLast(data); return; } ListNode cur = findIndex(index); ListNode node = new ListNode(data); node.next = cur.next; cur.next = node; }⑧删除第一次出现关键字为key的节点
a.遍历找到key值所在的节点
b.使该节点的前一位的指针域直接指向该节点后一位的指针域
public ListNode searchPery(int key) { ListNode cur = this.head; while (cur.next != null) { if (cur.next.val == key) { return cur;//是就是直接读取 } cur = cur.next;//不等于就接着往后面找 } return null; } //删除第一次出现关键字为key的节点 public void remove(int key) { if (this.head == null) { System.out.println("此链表为空链表！不能删除"); return; } if (this.head.val == key) { this.head = this.head.next; } ListNode cur = searchPery(key); if (cur == null) { System.out.println("没有你要删除的节点！"); return; } ListNode del = cur.next; cur.next = del.next; }⑨删除所有值为key的节点
a.遍历找到a的位置
b.对key值节点进行删除，需要注意的是，由于删除的节点不止一个，因此，我们需要记住被删除节点的前一个节点的位置，否则就会丢失单链表
代码：
public void removeAllKey(int key) { if(this.head==null){ return ; } ListNode prev=this.head; ListNode head=this.head.next; //先不判断头节点 while(cur！=null){ if(cur.val==key){ prev.next=cur.next; cur=cur.next; }else{ cur=prev; cur=cur.next; } } //处理头节点 if(this.head.val==key){ this.head=this.head.next; } }⑩清空链表
（即把每个位置的指针域置为null）
public void clear() { while (this.head != null) { ListNode curNext = head.next; this.head.next = null; this.head = curNext; } }
3.单链表典型操作
①反转链表
a.找一个prev节点，将其值置为空，其作用为将每个节点的指针域转换指向
b.找一个节点curNext记录cur即将要走的下一个位置
c.而cur的存在，当cur=null时，表明原链表以遍历到尾节点，将尾节点转换为头节点后，整个反转链表得以完成
代码：
public ListNode reverseList() { if(this.head==null){ return null; } ListNode cur=this.head; ListNode prev=null; while(cur!=null){ ListNode curNext=cur.next; cur.next=prev; prev=cur; cur=curNext; } return prev; }②找到链表中倒数第k个节点
a.设置fast,slow两个指针同时移动fast,slow节点
b.根据倒数第k个节点所离尾节点的位置，让fast节点先走对应的步数，然后当fast==null时，slow所指的位置即为倒数第k个节点的位置
代码：
public ListNode FindKthToTail(int k) { if(k<0||head==null){ System.out.println("此时找不到想要的节点"); } ListNode fast=this.head; ListNode slow=this.head; while(k-1!=0){ fast=fast.next; if(fast==null){ return null;} k--; } while(fast!=null&&fast.next!=null){ fast=fast.next; slow=slow.next; }return slow; }③找到一个x,以x为大小将一个链表分成两个部分，均不改变原来链表的顺序，最后连接在一起
a.题意为：根据x将值分为大于x的和小于x的分别放于两个不同的链表中，最后将两个链表连接在一起
b.需要创建两个新的链表as,ae=null;bs,be=null;
c.需要注意是否是第一次插入，以及是否只有一个链表的情况（即均大于或者均小于）
public ListNode partition(int x) { ListNode as=null; ListNode ae=null; ListNode bs=null; ListNode be=null; while(cur!=null){ if(cur.val<x){ //第一次插入值 if(as==null){ as=cur; ae=cur; }else{//非第一次插入值 ae.next=cur; ae=ae.next; } }else if(cur.val>=x){ if(bs==null){ bs=cur; be=cur; }else{//非第一次插入 be.next=cur; be=be.next; }cur=cur.next; } if (as == null) {//预防第一个节点所在的段为空,即没有比x小的数 return bs; } ae.next = bs; if (bs != null) {//保证最后一个节点为空 be.next = null; } return bs; }④判断链表是否是回文结构
a.要判断是否回文，首先要找到中间的节点，然后以中间节点为对称点，看是两端值是否一致这里可以设置两个指针一个fast,一个slow，fast一次两步，slow一次一步，当fast.next=null时,slow所指即为中间节点
b.找到中间值后，将后半部分进行链表的反转，反转后分别从两头进行比较值是否相等，若均相等则为回文结构，反之则不是回文结构
代码：?
public boolean chkPalindrome() { if(head==null){ return true; } ListNode fast=this.head; ListNode slow=this.head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; }//得到了中间值slow，下面进行反转链表 ListNode cur = slow.next;//将中间节点的next域置为null while (cur != null) { ListNode curNext = cur.next; cur.next = slow; slow = cur; cur = curNext; }//反转完成，下面开始判断是否回文 while (head != slow) {//此时反转后的链表的头节点为slow if (head.val != slow.val) {//只要有一对值不等，那么就返回false return false; } if (head.next.val == slow.val) {//表明只有两个节点 return true; } head = head.next; slow = slow.next; } return true; }⑤判断一个链表是否有环
(若是一个链表有环，那么易知，最后一个节点的指针域必然指向头节点)
a.同样设置fast和slow两个指针，一个一次两步，一个一次一步，若有环的话，两者必然会相遇，若两者不相遇，或者是快的指针指向了null,那么显然不存在环的结构
代码：?
public boolean hasCycle() { if (head == null) return false; ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } if (fast == null || fast.next == null) { return false; } return true; }⑥构造一个环进行操作
(实质上就是让尾节点的指针域指向头节点)
a.构造一个环
public void createLoop() { ListNode cur = this.head; while (cur.next != null) { cur = cur.next; } cur.next = head.next.next; }b.对环进行相应的操作，找相遇点，很明了是在已经是环的基础上进行的操作
//一个从头开始，一个从相遇点开始，最后相遇的地方就是入口点 public ListNode detectCycle() { if (head == null) return null; ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { break; } } if (fast == null || fast.next == null) { return null; } fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } }⑦合并两个有序的链表
a.要创建一个新的链表
b.将原来两个链表的值进行比较，谁小谁先插入新的链表
c.若是出现一者已经走完，则把另一个链表接连在后面即可
代码：
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode node = new ListNode(); ListNode tmp = node; while (l1 != null && l2 != null) { if (l1.val < l2.val) { tmp.next = l1; l1 = l1.next; tmp = tmp.next; } else { tmp.next = l2; l2 = l2.next; tmp = tmp.next; } } if (l1 != null) { tmp.next = l1; } if (l2 != null) { tmp.next = l2; } return node.next; } }
欢迎观看~
?
?