预览

  1. 反转链表中抓住核心步骤 cur.next=pre，在其之前以避免cur.next节点的覆盖为原则进行保存temp=cur.next，在其之后为下一步进行准备 cur=temp;
  2. 环形链表与Floyd判圈算法
  3. 合并链表
  4. 哑结点

206. 反转链表

经典题目了，三种思路，迭代、递归、存储在栈中再倒出来。迭代难度最大，附代码：

  1. public ListNode reverseList(ListNode head) {
  2.     ListNode temp=null;
  3.     ListNode pre=null;
  4.     ListNode cur=head;
  5.     while(cur!=null){
  6.       temp=cur.next;    // 2. 由于cur.next会在下一步被覆盖，先存在temp里
  7.       cur.next=pre;        // 1. 核心步骤
  8.       pre=cur;                // 3. 向前轮转
  9.       cur=temp;
  10.     }
  11.     return pre;
  12. }

141. 环形链表

经典题目了，两种思路，用哈希表存储已走过的节点；或者快慢指针重合判圈。后者空间复杂度低。

  1. public boolean hasCycle(ListNode head) {
  2.     if(head==null || head.next==null) return false;
  3.     ListNode fast=head;
  4.     ListNode slow=head;
  5.     do{
  6.         if(fast==null || fast.next==null) {
  7.             return false;
  8.         }
  9.         fast=fast.next.next;
  10.         slow=slow.next;
  11.     } while(fast!=slow);
  12.     return true;
  13. }

21. 合并两个有序链表

经典题目，有迭代与递归两种做法。核心思想就是每次将两个列表中头结点较小的那个头结点接在合并链表之后，重复该操作直到有一方为空，然后将非空的一方全部接到合并链表之后。用prev标识合并链表的最后一个节点，注意不要遗漏prev=prev.next。

  1. // 迭代法
  2. public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  3.     ListNode preHead=new ListNode(-1);
  4.     ListNode prev=preHead;
  5.     while(list1!=null && list2!=null){
  6.         if(list1.val<=list2.val){
  7.             prev.next=list1;
  8.             list1=list1.next;
  9.         }else{
  10.             prev.next=list2;
  11.             list2=list2.next;
  12.         }
  13.         prev=prev.next;
  14.     }
  15.     // 将非空的一个列表接在后面
  16.     if(list1!=null){
  17.         prev.next=list1;
  18.     }else{
  19.         prev.next=list2;
  20.     }
  21.     return preHead.next;
  22. }
  1. // 递归
  2. public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  3.     if(list1==null) return list2;
  4.     if(list2==null) return list1;
  5.     if(list1.val<=list2.val){
  6.         list1.next = mergeTwoLists(list1.next, list2);
  7.         return list1;
  8.     }else{
  9.         list2.next = mergeTwoLists(list1, list2.next);
  10.         return list2;
  11.     }
  12. }

该题变种：23. 合并K个升序链表。最简单的实现是循环K-1次的两有序列表合并。通过分治法，两两合并，合并后再两两合并，可以缩减时间复杂度。

19. 删除链表的倒数第 N 个结点

经典题目。核心在于找到待删除节点的前一个节点。用快慢指针实现，具体实现中用哑结点（头结点之前的虚拟节点）可以避免删除头结点时这一特殊情况的处理。