1、剑指 Offer 22.链表中倒数第k个节点

1.1 题目

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：

给定一个链表: 1->2->3->4->5, 和 k = 2。返回链表 4->5.

1.2 思路

本题有2种思路：

  1. 第一次遍历链表，求链表长度；第二次遍历链表，结合k求出在哪个下标停止遍历，但需要遍历两次。
  2. 快慢指针。快指针先移动k次，然后快慢指针一起移动，直到快指针为null，此时慢指针指向的节点即倒数第k个节点。

本题采用第二种解法，注意返回的是slow而不是slow.next。

1.3 代码

  1. class Solution {
  2.     public ListNode getKthFromEnd(ListNode head, int k) {
  3.         ListNode fast = head, slow = head;
  4.         for (int i = 0; i < k; ++i) {
  5.             fast = fast.next;
  6.         }
  7.         while (fast != null) {
  8.             fast = fast.next;
  9.             slow = slow.next;
  10.         }
  11.         return slow;
  12.     }
  13. }

2、剑指 Offer 06.从尾到头打印链表

2.1 题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：

输入：head = [1,3,2] 输出：[2,3,1]。

2.2 思路

本题有两种思路：

  • 用额外的数据结构，比如栈去存储正向遍历链表获取的数据，然后再遍历栈，将栈中的元素存储到数组中返回；
  • 不用额外的数据结构，在链表本身进行链表反转，然后遍历反转后的链表，将元素依次放入数组中返回。

本题采用第二种思路，尽量复用之前的引用，比如第二次遍历以pre为头结点的反转后的链表，将cur引用作为工作指针指向pre链表头结点，不需要再新建额外的工作指针指向pre头结点了。注意反转链表尽量在链表本身进行反转，不要借助额外的数据结构占用存储空间。

2.3 代码

  1. class Solution {
  2.     public int[] reversePrint(ListNode head) {
  3.         ListNode pre = null;
  4.         ListNode cur = head;
  5.         int cnt = 0;
  6.         while (cur != null) {
  7.             ListNode next = cur.next;
  8.             cur.next = pre;
  9.             pre = cur;
  10.             cur = next;
  11.             ++cnt;
  12.         }
  14.         int[] res = new int[cnt];
  15.         cnt = 0;
  16.         cur = pre;
  17.         while (cur != null) {
  18.             res[cnt] = cur.val;
  19.             cur = cur.next;
  20.             ++cnt;
  21.         }
  22.         return res;
  23.     }
  24. }

3、剑指 Offer 24.反转链表

3.1 题目

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

3.2 思路

本题有两个思路：

  • 迭代：只在原链表空间上进行反转。
  • 递归：不太好想。

    3.3 代码

    迭代：
    1. class Solution {
    2.   private ListNode pre;
    3.   public ListNode reverseList(ListNode head) {
    4.       ListNode cur = head;
    5.       while (cur != null) {
    6.           ListNode next = cur.next;
    7.           cur.next = pre;
    8.           pre = cur;
    9.           cur = next;
    10.       }
    11.       return pre;
    12.   }
    13. }
    递归：
    1. class Solution {
    2.   private ListNode head;
    3.   public ListNode reverseList(ListNode head) {
    4.       if (head == null || head.next == null) {
    5.           return head;
    6.       }
    7.       ListNode resNode = reverseList(head.next);
    8.       head.next.next = head;
    9.       head.next = null;
    10.       return resNode;
    11.   }
    12. }

    4、剑指 Offer 25.合并两个排序的链表

    4.1 题目

    输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
    示例1：

    输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4

4.2 思路

有两种思路：

  • 同时遍历两个链表，将链表当前的temp指针对应的节点的值进行比较，值小的插入新的链表，工作指针向后移一位。如果其中一个工作指针为null，将另一个链表的工作指针拼接；
  • dfs，代码比较简洁。

本题采用dfs的方法。

4.3 代码

  1. class Solution {
  2.     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
  3.         if (l1 == null) {
  4.             return l2;
  5.         }
  6.         if (l2 == null) {
  7.             return l1;
  8.         }
  9.         if (l1.val <= l2.val) {
  10.             l1.next = mergeTwoLists(l1.next, l2);
  11.             return l1;
  12.         } else {
  13.             l2.next = mergeTwoLists(l1, l2.next);
  14.             return l2;
  15.         }
  16.     }
  17. }

5、剑指 Offer 35.复杂链表的复制

5.1 题目

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
image.png

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：
image.png

输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]

示例 3：
image.png

输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]

示例 4：

输入：head = [] 输出：[] 解释：给定的链表为空（空指针），因此返回 null。

5.2 思路

感觉这道题的思路不具备普适性，像是专门为这道题准备的思路。

  1. 遍历原链表，并将原链表改编成下面的新链表：

node1 -> new1 -> node2 -> new2 -> node3 -> new3

  1. 遍历新链表，对新节点的random指针赋值，关键代码：cur.next.random = cur.random.next;

  2. 遍历2中处理后的新链表，原来的老链表和最终返回的链表从新链表中依次断开，注意最后要处理老链表的最后一个节点，另其next指向null，否则其next依然指向返回链表的最后一个node。

    5.3 代码

    1. class Solution {
    2.  public Node copyRandomList(Node head) {
    3.      if (head == null) {
    4.          return head;
    5.      }
    7.      Node cur = head;
    8.      while (cur != null) {
    9.          Node node = new Node(cur.val);
    10.          node.next = cur.next;
    11.          cur.next = node;
    12.          cur = node.next;
    13.      }
    15.      cur = head;
    16.      while (cur != null) {
    17.          if (cur.random != null) {
    18.              cur.next.random = cur.random.next;
    19.          }
    20.          cur = cur.next.next;
    21.      }
    23.      Node res = head.next;
    24.      cur = res;
    25.      Node old = head;
    26.      while (cur.next != null) {
    27.          old.next = cur.next;
    28.          old = old.next;
    29.          cur.next = cur.next.next;
    30.          cur = cur.next;
    31.      }
    32.      old.next = null;
    33.      return res;
    34.  }
    35. }

    6、剑指 Offer 52.两个链表的第一个公共节点

    6.1 题目

    输入两个链表，找出它们的第一个公共节点。
    示例1：
    image.png
    第一个公共节点是8。

    8是第一个公共节点，1是第一个内容相同的节点。所谓的公共节点，节点前一个节点和后一个节点值均相等。

6.2 思路

参考：https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/solution/jian-zhi-offer-52-liang-ge-lian-biao-de-gcruu/
这种思路感觉普适性也不大。
算法思想：

  1. 指针A先遍历headA，如果遍历到headA的尾部（尾部是指null节点，而不是headA的最后一个非null节点），就继续从headB开始遍历；
  2. 指针B先遍历headB，如果遍历到headB的尾部，就继续从headA开始遍历；

  3. 当指针A和指针B相等时，即是两个指针相遇的时刻，此时返回指针A和指针B中的任意一个，即是第一个相遇节点。

    6.3 代码

    1. public class Solution {
    2.  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    3.      if (headA == null || headB == null) {
    4.          return null;
    5.      }
    6.      ListNode tmp1 = headA;
    7.      ListNode tmp2 = headB;
    8.      while (tmp1 != tmp2) {
    9.          // 注意这里是tmp1 == null, 而不是tmp1.next == null
    10.          tmp1 = tmp1 == null? headB: tmp1.next;
    11.          tmp2 = tmp2 == null? headA: tmp2.next;
    12.      }
    13.      return tmp1;
    14.  }
    15. }

    7、剑指 Offer 36.二叉搜索树与双向链

    好鸡儿难想啊……

    7.1 题目

    输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。为了让您更好地理解问题，以下面的二叉搜索树为例：
    链表 - 图5
    我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
    链表 - 图6
    特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

    7.2 思路

    二叉搜索树中序遍历，得到的val会按升序排序，因此本题的dfs为中序遍历。

  4. 需要维护两个private成员变量head、pre，head为生成的双向循环链表的头结点，pre为双向循环链表的前一个节点，最终pre为最后一个节点；

  5. 当pre为null时，说明此时的cur正是头结点，令head指向cur；
  6. 二叉搜索树每轮dfs，令pre.right = cur, cur.left = pre;

  7. 最后需要处理head和pre，让其互指，构成循环链表。

    7.3 代码

    1. class Solution {
    2.  private Node pre;
    3.  private Node head;
    4.  public Node treeToDoublyList(Node root) {
    5.      if (root == null) {
    6.          return null;
    7.      }
    8.      dfs(root);
    9.      pre.right = head;
    10.      head.left = pre;
    11.      return head;
    12.  }
    14.  private void dfs(Node cur) {
    15.      if (cur == null) {
    16.          return;
    17.      }
    18.      dfs(cur.left);
    19.      if (pre == null) {
    20.          head = cur;
    21.      } else {
    22.          pre.right = cur;
    23.      }
    24.      cur.left = pre;
    25.      pre = cur;
    26.      dfs(cur.right);
    27.  }
    28. }

    8、剑指 Offer 18.删除链表的节点

    8.1 题目

    给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
    示例 1:

    输入: head = [4,5,1,9], val = 5 输出: [4,1,9] 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1 输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

8.2 思路

遍历链表的时候需要维护上一个节点pre的值，当遇到cur.val == val时，退出遍历循环，然后令pre.next = cur.next即可。需要注意当val的值就是链表头结点时，需要对这种边界条件做特殊处理。

8.3 代码

  1. class Solution {
  2.     public ListNode deleteNode(ListNode head, int val) {
  3.         if (head.val == val) {
  4.             return head.next;
  5.         }
  6.         ListNode pre = null;
  7.         ListNode cur = head;
  8.         while (cur != null && cur.val != val) {
  9.             pre = cur;
  10.             cur = cur.next;
  11.         }
  12.         pre.next = cur.next;
  13.         return head;
  14.     }
  15. }

9、合并K个升序链表

9.1 题目

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6

示例 2：

输入：lists = [] 输出：[]

示例 3：

输入：lists = [[]] 输出：[]

9.2 思路

分治/归并合并k个排序链表。

  1. 对这k个排序链表组成的数组进行分治划分：从中间划分为左右两部分，左右两部分依次再从中间划分为左右两部分，直到划分到最底层时返回的是单个链表，这时就需要对两个链表进行合并排序，从底向上两两合并；

  2. 对两个排序链表合并成一个链表，并返回链表的头节点：这其实也是一个独立的题目，即合并两个排序链表，有两种方法：

    1. 同时遍历两个链表，依次比较头节点的值，再组装成一个新的链表返回；

    2. 用递归的思想，也是本题用的方法。

      9.3 代码

      1. class Solution {
      2. public ListNode mergeKLists(ListNode[] lists) {
      3.   return merge(lists, 0, lists.length - 1);
      4. }
      6. private ListNode merge(ListNode[] lists, int left, int right) {
      7.   if (left == right) {
      8.       return lists[left];
      9.   }
      10.   if (left > right) {
      11.       return null;
      12.   }
      13.   int mid = (left + right) >> 1;
      14.   return mergeTwoList(merge(lists, left, mid), merge(lists, mid + 1, right));
      15. }
      17. private ListNode mergeTwoList(ListNode head1, ListNode head2) {
      18.   if (head1 == null) {
      19.       return head2;
      20.   }
      21.   if (head2 == null) {
      22.       return head1;
      23.   }
      24.   if (head1.val <= head2.val) {
      25.       head1.next = mergeTwoList(head1.next, head2);
      26.       return head1;
      27.   } else {
      28.       head2.next = mergeTwoList(head1, head2.next);
      29.       return head2;
      30.   }
      31. }
      32. }

      下面这种写法更贴近归并排序的模板：

      1. class Solution {
      2. public ListNode mergeKLists(ListNode[] lists) {
      3.   if (lists == null || lists.length == 0) {
      4.       return null;
      5.   }
      6.   return merge(lists, 0, lists.length - 1);
      7. }
      9. private ListNode merge(ListNode[] lists, int left, int right) {
      10.   if (left < right) {
      11.       int mid = (left +right) >> 1;
      12.       ListNode leftNode = merge(lists, left, mid);
      13.       ListNode rightNode = merge(lists, mid + 1, right);
      14.       return mergeSort(leftNode, rightNode);
      15.   }
      16.   return lists[left];
      17. }
      19. private ListNode mergeSort(ListNode head1, ListNode head2) {
      20.   if (head1 == null) {
      21.       return head2;
      22.   }
      23.   if (head2 == null) {
      24.       return head1;
      25.   }
      26.   if (head1.val < head2.val) {
      27.       head1.next = mergeSort(head1.next, head2);
      28.       return head1;
      29.   } else {
      30.       head2.next = mergeSort(head1, head2.next);
      31.       return head2;
      32.   }
      33. }
      34. }

      10、148. 排序链表

      这道题跟上面合并k个升序链表的思路很像，都是分治。

      10.1 题目

      给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

      10.2 思路

      整体思路还是用分治的思想，先分（划分排序链表），再治（合并两个排序链表），这题用到了三个题目：

  3. 划分排序链表，注意返回条件（链表为null或者链表仅有一个元素，就返回）；

  4. 取链表中间的节点，这里是快慢指针求链表中点的题目，注意链表跟数组还不完全一样，找到链表中点后，要把对应的尾节点置为null；

  5. 合并两个排序链表的题目，可以递归或者依次遍历。

    10.3 代码

    1. class Solution {
    2.  public ListNode sortList(ListNode head) {
    3.      if (head == null || head.next == null) {
    4.          return head;
    5.      }
    7.      ListNode mid = getMid(head);
    8.      ListNode tmp = mid.next;
    9.      mid.next = null;
    10.      return mergeTwo(sortList(head), sortList(tmp));
    11.  }
    13.  private ListNode getMid(ListNode head) {
    14.      ListNode fast = head, slow = head;
    15.      while (fast.next != null && fast.next.next != null) {
    16.          fast = fast.next.next;
    17.          slow = slow.next;
    18.      }
    19.      return slow;
    20.  }
    22.  private ListNode mergeTwo(ListNode head1, ListNode head2) {
    23.      if (head1 == null) {
    24.          return head2;
    25.      }
    26.      if (head2 == null) {
    27.          return head1;
    28.      }
    29.      if (head1.val < head2.val) {
    30.          head1.next = mergeTwo(head1.next, head2);
    31.          return head1;
    32.      } else {
    33.          head2.next = mergeTwo(head1, head2.next);
    34.          return head2;
    35.      }
    36.  }
    37. }

    11、234. 回文链表

    11.1 题目

    给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

    11.2 思路

  6. 通过快慢指针直到链表的中间位置节点；

  7. 将中间节点之后的链表反转；
  8. 将前一半链表和后一半反转后的链表逐一比较。

这道题跟之前做的回文字符串有一点不一样：回文字符串需要考虑奇数长度的字符串和偶数长度的字符串，回文链表的中间点选取不需要考虑链表长度的奇偶性，因为最后遍历两个链表的时候，可能反转后的链表没有遍历完全。

11.3 代码

  1. class Solution {
  2.     public boolean isPalindrome(ListNode head) {
  3.         if (head == null) {
  4.             return true;
  5.         }
  6.         // 快慢指针找到中间点
  7.         ListNode slow = head, fast = head, pre = null;
  8.         while (fast != null && fast.next != null) {
  9.             fast = fast.next.next;
  10.             slow = slow.next;
  11.         }
  13.         // 翻转中间的之后的链表
  14.         while (slow != null) {
  15.             ListNode next = slow.next;
  16.             slow.next = pre;
  17.             pre = slow;
  18.             slow = next;
  19.         }
  21.         // 依次遍历两个链表比较
  22.         while (head != null && pre != null) {
  23.             if (head.val != pre.val) {
  24.                 return false;
  25.             }
  26.             head = head.next;
  27.             pre = pre.next;
  28.         }
  29.         return true;
  30.     }
  31. }

12、141. 环形链表

12.1 题目

给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 ，则返回 true 。 否则，返回 false 。
image.png

12.2 思路

环形链表判断是否有环，就用快满指针，起始位置都是从head出发，快指针一次走两格，慢指针一次走一格，如果快慢指针能再次相遇，则代表有环。

12.3 代码

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

13、142. 环形链表 II

13.1 题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改链表。
image.png

13.2 思路

环形链表求入环点的固定步骤：

  1. 快慢指针，初始位置都在头结点；
  2. 快指针一次走两格，慢指针一次走一格；
  3. 当快慢指针第一次相遇时，将快指针重新指向头结点；

  4. 快满指针每次均走一格，直到快满指针再次相遇，返回slow或者fast中任意一个即是入环点。

    13.3 代码

    1. public class Solution {
    2.  public ListNode detectCycle(ListNode head) {
    3.      if (head == null || head.next == null) {
    4.          return null;
    5.      }
    6.      ListNode fast = head;
    7.      ListNode slow = head;
    8.      while (fast != null && fast.next != null) {
    9.          fast = fast.next.next;
    10.          slow = slow.next;
    11.          if (fast == slow) {
    12.              fast = head;
    13.              while (fast != slow) {
    14.                  fast = fast.next;
    15.                  slow = slow.next;
    16.              }
    17.              return slow;
    18.          }
    19.      }
    20.      return null;
    21.  }
    22. }

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

    14.1 题目

    给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
    image.png

    14.2 思路

    本题跟第一道求链表中倒数第k个节点的思路是一样的。本题有两种思路：

  5. 先求链表长度，然后计算出终止的迭代次数，然后再遍历链表，这样时间复杂度上要遍历两次链表；

  6. 用快慢指针的方法，但是要注意删除链表头结点这种特殊情况。

以快慢指针方法说明：

  1. 令快指针指向头结点，向后迭代n次；
  2. 判断此时快指针是否为null，如果为null，说明是删除的是头结点，直接返回head.next；
  3. 令慢指针指向头结点，快慢指针一起每次向后移动一格，同时维护一个pre指针，令pre指向上次迭代的slow，直到快指针指向null，while循环结束；
  4. 此时慢指针指向的节点即为链表中倒数第n个节点；

  5. 令pre.next = slow.next，然后返回head即可。

    14.3 代码

    先求链表长度，在逐一遍历：

    1. class Solution {
    2.  public ListNode removeNthFromEnd(ListNode head, int n) {
    3.      int len = getLength(head);
    4.      if (n == len) {
    5.          return head.next;
    6.      }
    7.      int index = len - n;
    8.      ListNode pre = null;
    9.      ListNode tmp = head;
    10.      for (int i = 0; i < index; ++i) {
    11.          pre = tmp;
    12.          tmp = tmp.next;
    13.      }
    14.      pre.next = tmp.next;
    15.      return head;
    16.  }
    18.  private int getLength(ListNode head) {
    19.      int len = 0;
    20.      ListNode tmp = head;
    21.      while (tmp != null) {
    22.          ++len;
    23.          tmp = tmp.next;
    24.      }
    25.      return len;
    26.  }
    27. }

    双指针巧妙定位链表倒数第k个节点：

    1. class Solution {
    2.  public ListNode removeNthFromEnd(ListNode head, int n) {
    3.      ListNode fast = head, slow = head;
    4.      for (int i = 0; i < n; ++i) {
    5.          fast = fast.next;
    6.      }
    7.      // 当删除的是头结点时
    8.      if (fast == null) {
    9.          return head.next;
    10.      }
    11.      ListNode pre = null;
    12.      while (fast != null) {
    13.          pre = slow;
    14.          slow = slow.next;
    15.          fast = fast.next;
    16.      }
    17.      pre.next = slow.next;
    18.      return head;
    19.  }
    20. }

    15、剑指 Offer II 025. 链表中的两数相加

    15.1 题目

    给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。可以假设除了数字 0 之外，这两个数字都不会以零开头。
    image.png

    15.2 思路

  6. 相加包含了进位，且是右边为低位，因此需要先将两个链表反转，再从反转后的链表开始遍历，且最后相加得到的链表，也需要反转才是最后的结果，因此需要先实现一个公共函数：反转链表，返回反转后的链表头结点；

  7. 本题最精髓的就是这个while循环判断条件：while (l1 != null || l2 != null || carry != 0) ，不然越写代码需要判断的条件就越多；

  8. 注意sum % 10是对应位的相加结果，sum / 10是进位值。

    15.3 题目

    1. class Solution {
    2.  public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    3.      if (l1 == null) {
    4.          return l2;
    5.      }
    6.      if (l2 == null) {
    7.          return l1;
    8.      }
    10.      l1 = reverse(l1);
    11.      l2 = reverse(l2);
    12.      ListNode head = new ListNode(0);
    13.      ListNode tmp = head;
    14.      int carry = 0;
    15.      while (l1 != null || l2 != null || carry != 0) {
    16.          int sum = carry;
    17.          if (l1 != null) {
    18.              sum += l1.val;
    19.              l1 = l1.next;
    20.          }
    21.          if (l2 != null) {
    22.              sum += l2.val;
    23.              l2 = l2.next;
    24.          }
    25.          tmp.next = new ListNode(sum % 10);
    26.          carry = sum / 10;
    27.          tmp = tmp.next;
    28.      }
    29.      return reverse(head.next);
    30.  }
    32.  private ListNode reverse(ListNode node) {
    33.      ListNode pre = null;
    34.      ListNode tmp = node;
    35.      while (tmp != null) {
    36.          ListNode next = tmp.next;
    37.          tmp.next = pre;
    38.          pre = tmp;
    39.          tmp = next;
    40.      }
    41.      return pre;
    42.  }
    43. }

    16、82. 删除排序链表中的重复元素 II

    16.1 题目

    给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
    image.png

    16.2 思路

    整体思路还是遍历一次链表，就在链表本身进行断开连接操作。

  9. 由于链表的头节点也有可能重复被删除，因此需要引入一个哑节点dummy，这个哑节点的值为0，next指针指向head，结果返回的时候就返回dummy.next；

  10. 声明一个指向dummy的引用cur，通过这个cur遍历链表，注意while循环条件是根据循环体里的取值判空的；
  11. 比较的是cur.next.val == cur.next.next.val，如果相等，记录一下此时的cur.next.val，再向后遍历看有多少个节点的值是x，向后遍历过程中都在更新cur.next。

    16.3 代码

    1. class Solution {
    2.  public ListNode deleteDuplicates(ListNode head) {
    3.      if (head == null) {
    4.          return head;
    5.      }
    6.      ListNode dummy = new ListNode(0, head);
    7.      ListNode cur = dummy;
    8.      while (cur.next != null && cur.next.next != null) {
    9.          if (cur.next.val == cur.next.next.val) {
    10.              int x = cur.next.val;
    11.              while (cur.next != null && cur.next.val == x) {
    12.                  cur.next = cur.next.next;
    13.              }
    14.          } else {
    15.              cur = cur.next;
    16.          }
    17.      }
    18.      return dummy.next;
    19.  }
    20. }

    17、92. 反转链表 II

    建议背诵……

    17.1 题目

    image.png

    17.2 思路

    todo：图

    17.3 代码

    1. class Solution {
    2.  public ListNode reverseBetween(ListNode head, int left, int right) {
    3.      if (head == null) {
    4.          return null;
    5.      }
    6.      ListNode dummy = new ListNode(0, head);
    7.      // pre永远指向待反转区域的左边界的上一个节点
    8.      ListNode pre = dummy;
    9.      for (int i = 0; i < left - 1; ++i) {
    10.          pre = pre.next;
    11.      }
    12.      // cur起始位置是left，在遍历过程中向后移动
    13.      ListNode cur = pre.next;
    14.      // 遍历过程就是当前cur.next头插到pre节点之后的过程
    15.      for (int i = 0; i < right - left; ++i) {
    16.          // next永远是cur的下一个节点
    17.          ListNode next = cur.next;
    18.          cur.next = next.next;
    19.          next.next = pre.next;
    20.          pre.next = next;
    21.      }
    22.      return dummy.next;
    23.  }
    24. }