算法训练营day04 | {24.两两交换链表中的节点, 19.删除链表的倒数第N个节点, 160. 链表相交，142. 环形链表II}

第二章链表-part02，知识点为快慢双指针、哈希表。

24. 两两交换链表中的节点

• 题目链接：24. 两两交换链表中的节点
• 文档讲解：代码随想录–24. 两两交换链表中的节点
• 视频讲解：帮你把链表细节学清楚！ | LeetCode：24. 两两交换链表中的节点
• 状态：我傻了，这题需要前后4个结点参与链表操作。

1.1 看完代码随想录的想法

• 需要画图，然后两两交换结点的过程中，这两个结点的前一个结点也需要参与更改索引，实现：
  ▶

  AC解法

  class Solution {
      public ListNode swapPairs(ListNode head) {
          ListNode dummy = new ListNode(0);
          ListNode dummyHead = new ListNode(0);
          dummyHead.next = head;
          ListNode cur = dummyHead;
          while(cur.next != null && cur.next.next != null) {
              ListNode temp = cur.next;
              ListNode temp1 = cur.next.next.next;
              cur.next = temp.next;
              temp.next.next = temp;
              temp.next = temp1;
              cur = cur.next.next;  // 后移两格
          }
          return dummyHead.next;
      }
  }

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

• 题目链接：19. 删除链表的倒数第N个节点
• 文档讲解：代码随想录–19.删除链表的倒数第N个节点
• 视频讲解：链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点
• 状态：快慢指针法，不过注意快指针是先走n+1步，这样慢指针就落在要删除的结点的前一个位置上。

2.1 看完代码随想录的想法

• 同样是双指针的典型应用，数组和链表的题目前遇到很多双指针的解法了。
• 设置一个虚拟头结点，方便统一所有位置的删除逻辑。
• 以及注意为了防止fast.next报空指针异常，选择在前面n++，然后再进入循环，省去一个if判断。

▶

删除链表的倒数第N个节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode fast = dummyHead, slow = dummyHead;
        n++;
        while(n > 0 && (null != fast)) {
            n--;
            fast = fast.next;
        }
        while(null != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyHead.next;
    }
}

160. 链表相交

• 题目链接：160.链表相交
• 文档讲解：代码随想录–160.链表相交
• 状态：做题之前已经提示了数值相同，不一定索引地址相同，本题应该找到地址相同的结点。

3.1 解题过程

• 两次计算链表的长度，然后让长的链表的后半段和短链表对齐，再同步移动，这个思路比较简单，但是时间复杂度是O(n+m)，而且代码太长。

• （解法一）用哈希表解决这题非常合适，set.contains(Object o)直接判断结点是否重复，就是空间复杂度为O(n)

  ▶

  哈希表

  public class Solution {
      public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
          HashSet<ListNode> mySet = new HashSet<>();
          while(headA != null) {
              mySet.add(headA);
              headA = headA.next;
          }
          while(headB != null) {
              if (mySet.contains(headB)) {
                  return headB;
              }
              headB = headB.next;
          }
          return null;   
      }
  }

• （解法二）链表1长度A+C，链表2长度B+C，则 A+C+B 一定等于 B+C+A。

  ▶

  A+C+B=B+C+A

  public class Solution {
      public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
          ListNode A =headA, B = headB;
          while(A!=B){
              A = A==null? headB:A.next;
              B = B==null? headA:B.next;
          }
          return A;
      }
  }

142. 环形链表II

• 题目链接：142. 环形链表II
• 文档讲解：代码随想录–142. 环形链表II
• 状态：没做出来。

4.1 解题过程

• （解法一）画图设未知变量就清楚了，fast指针不管在圈里转了几圈都无所谓，当slow指针进入入口时，这时候的相对位置才重要。

  ▶

  快慢双指针

  public class Solution {
      public ListNode detectCycle(ListNode head) {
           ListNode fast=head;
          ListNode slow=head;
          while(fast!=null&&fast.next!=null){
              fast=fast.next.next;
              slow=slow.next;
              if(fast==slow){
                  while(slow!=head){
                      slow=slow.next;
                      head=head.next;
                  }
                  return slow;
              }
          }
          return null;
      }
  }

• （解法二）哈希表非常简单了，挨个存入哈希Set，存之前判断是否已经在Set中。

• ▶

  哈希表

  public class Solution {
      public ListNode detectCycle(ListNode head) {
          HashSet<ListNode> mySet = new HashSet<>();
          while(head != null) {
              if (mySet.contains(head)) {
                  return head;
              }
              mySet.add(head);
              head = head.next;
          }
          return null;
      }
  }

5. 链表总结

• 不管是增删操作，还是查询操作，给链表设置一个统一的虚拟头结点，总是方便的。
• 关于原地反转链表，用到了双指针，并且需要头结点；
• 关于删除倒数第N个结点、环形列表II（解法一），也用到了双指针（快慢双指针版）；
• 关注链表相交，解法2也是双指针；可见双指针思想非常重要。
• 如果题目涉及是否存在重复问题，利用哈希表不可重复的特性也是一种非常优雅而且简单的解法。