【算法】链表

  零：链表常用技巧

1：引入虚拟头结点

（1）便于处理边界情况

（2）方便我们对链表操作

2：两步尾插，头插 

（1）尾插

tail指向最后一个节点，tail.next 指向新尾节点，tail指针在指向新尾节点

（2）头插

新头结点.next = 虚拟头节点newhead.next

虚拟头节点newhead.next = 新头结点.

3：插入节点 

若有一个指针（next）指向被插入节点后的那个节点，那么这四句代码的顺序随意

反之，前两句必须写在前面（这两句顺序可以互换），后两句必须写在后面

一： 两数相加

2. 两数相加

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//先new一个虚拟节点ListNode newHead = new ListNode(0);ListNode cur1 = l1 , cur2 = l2, cur3 = newHead;int t = 0;while(cur1 != null || cur2 != null || t != 0){//对第一个链表做加法if(cur1 != null){t += cur1.val;cur1 = cur1.next;}//对第二个链表做加法if(cur2 != null){t += cur2.val;cur2 = cur2.next;}//移动cur3.next = new ListNode(t%10);cur3 = cur3.next;t = t/10;}return newHead.next;}
}

二：两两交换链表中的节点

两两交换链表中的节点

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}// 虚拟头结点ListNode newHead = new ListNode(0);newHead.next = head;// 先搞四个指针ListNode prev = newHead, cur = prev.next, next = cur.next, nnext = next.next;while (cur != null && next != null) {prev.next = next;next.next = cur;cur.next = nnext;prev = cur;cur = nnext;if (cur != null) {next = cur.next;}if (next != null) {nnext = next.next;}}return newHead.next;}
}

三：143. 重排链表（写的酣畅淋漓的一道题 ）

这道题涵盖了双指针，前插，尾插，合并两个链表，代码调试也很爽，很重要的是我们在变量的选择和名称定义上一定要规范，否则写代码就是一种折磨

 

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public void reorderList(ListNode head) {if(head == null || head.next == null || head.next.next == null) return ;// 1:找中间节点ListNode fast = head;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}// 逆序准备工作：新的头结点ListNode head1 = head;ListNode head2 = new ListNode(0);ListNode cur = slow.next;slow.next = null;// 将上半段尾插null，分开标志// 2：逆序头插(很明显头插一直要用到的指针是头结点，这是关键)，这里逆序链表头结点是虚拟节点注意注意！！！！while (cur != null) {ListNode tmp = cur.next;cur.next = head2.next;head2.next = cur;// cur = cur.next;错的cur更新为tmp，cur.next已经指向null了cur = tmp;}// 3:合并两个链表(尾插)双指针ListNode ret = new ListNode(0);ListNode prev = ret;ListNode cur1 = head1, cur2 = head2.next;while (cur1 != null) {// 左半链表长度>=右半// 先插左prev.next = cur1;cur1 = cur1.next;prev = prev.next;//  在插右if (cur2 != null) {prev.next = cur2;cur2 = cur2.next;prev = prev.next;}}}
}

四：合并K个升序链表

 23. 合并 K 个升序链表

这道题的解法有三种，暴力解法（超时），优先级队列（文章写法），递归（难）

复习了优先级队列的lambda表达式写法，爽，战斗爽！AC爽

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeKLists(ListNode[] lists) {PriorityQueue<ListNode> queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);// 小根堆// 放入第一批头结点for (ListNode head : lists) {if (head != null) {queue.offer(head);}}// 合并链表ListNode ret = new ListNode(0);ListNode cur = ret;// 定义指针while (!queue.isEmpty()) {ListNode tmp = queue.poll();cur.next = tmp;cur = cur.next;if (tmp.next != null) {tmp = tmp.next;queue.offer(tmp);}}return ret.next;}
}

五：K个一组翻转链表

25. K 个一组翻转链表

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseKGroup(ListNode head, int k) {// 第一步计算需要逆序多少组 int n = 0;ListNode cur = head;while(cur != null){n++;cur = cur.next;}n = n/k;//逆序组数ListNode tmp = head;ListNode ret = new ListNode(0);ListNode prev = ret;while(n != 0){ListNode move = tmp;int m = k;while(m != 0){//执行k次头插法ListNode next = tmp.next;tmp.next = prev.next;prev.next = tmp;tmp = next;m--;}prev = move;n--;}prev.next = tmp;return ret.next;}
}

六：相交链表

力扣k神的图解，真的nb，太清晰了

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode A = headA, B = headB;while (A != B) {A = A != null ? A.next : headB;B = B != null ? B.next : headA;}return A;}
}

七：回文链表

心得：

1：尽量画图

2：确定中间节点的时候，奇数个节点好理解，偶数个节点指向的是右边那个节点

3：反转链表后原链表并没有断开

4：反转链表有两种方法，第一种搞一个虚拟头结点，进行头插，第二种递归。战斗爽！塔塔开

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {} *     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {//画个图就清晰多了，奇数个节点和偶数个节点public boolean isPalindrome(ListNode head) {ListNode mid = midNode(head);ListNode reverseHead = reverseList2(mid);//没有断while(reverseHead != null){if(head.val != reverseHead.val){return false;}head = head.next;reverseHead = reverseHead.next;}return true;}public ListNode midNode(ListNode head){//快慢双指针ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}return slow;}public ListNode reverseList(ListNode head){//new 虚拟null节点ListNode pre = null;ListNode cur = head;//头插while(cur != null){ListNode tmp = cur.next;cur.next = pre;pre = cur;cur = tmp;}return pre;}public ListNode reverseList2(ListNode head){//递归的方法，head等不等于null，就是以防给的是空链表if(head == null || head.next == null){return head;}ListNode newHead = reverseList(head.next);//新的头结点head.next.next = head;head.next = null;return newHead;}}