【算法】链表

零：链表常用技巧 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; } }  八：环形链表

心得：快慢双指针，秒了

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head == null) return false; ListNode slow = head, fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return true; } } return false; } }