双指针技巧秒杀链表 | 顾澜的技术小站

21. 合并两个有序链表

解题思路：

同时循环两个链表，去除较小的一个只放入新链表，直到其中一个节点为nil

示例代码：

// 分别取出两个链表的当前值比较,较小的赋值给新链表
// 初始化时需要声明一个虚拟节点,避免空指针
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
   head := &ListNode{}
   pre := head
   for list1 != nil && list2 != nil {
      // 比较两个节点的值, 将较小的节点放到pre指针
      if list1.Val < list2.Val {
         pre.Next = list1
         list1 = list1.Next
      } else {
         pre.Next = list2
         list2 = list2.Next
      }
      pre = pre.Next
   }

   if list1 != nil {
      pre.Next = list1
   }

   if list2 != nil {
      pre.Next = list2
   }
   return head.Next
}

23. 合并K个升序链表

解题思路：

简单粗暴，从第一个往后一依次合并

**进阶：**使用递归合并

示例代码：

func mergeKLists1(lists []*ListNode) *ListNode {
   pre := &ListNode{}
   cur := &ListNode{}
   if len(lists) == 0 {
      return nil
   }
   pre = lists[0]
   for i := 1; i < len(lists); i++ {
      cur = lists[i]
      pre = mergeTwoLists(pre, cur) // 21题函数
   }
   return pre
}

解题思路：

此题关键难点在于，如何快速从K个链表中找出最小节点

这里我们使用优先级队列（二叉堆）这种数据结构，构建一个最小堆，把所有链表节点放入其中，然后每次取出最小节点加入新链表即可。

注意：取出节点后需要将下一个节点放入最小堆中

示例代码：

// 使用最小堆存储所有链表头结点节点
// 遍历最小堆,取出最小节点添加到新链表,同时将取出节点下一个节点放入最小堆中
func mergeKLists(lists []*ListNode) *ListNode {
   h := new(minHeap)
   // 将所有链表的头结点放入最小堆
   for _, list := range lists {
      if list != nil {
         heap.Push(h, list)
      }
   }

   head := &ListNode{}
   pre := head
   for h.Len() > 0 {
      // 取出最小节点
      node := heap.Pop(h).(*ListNode)
      if node.Next != nil {
         // 将最小节点下一节点加入最小堆
         heap.Push(h, node.Next)
      }
      // 最小节点放入链表
      pre.Next = node
      pre = pre.Next
   }
   return head.Next
}

86. 分隔链表

解题思路：

遍历原链表，根据需求把链表分成两个小链表，一个链表所有元素小于x，另一个链表所有元素大于等于x，最后把两个链表连接到一起就可以了。

示例代码：

func partition(head *ListNode, x int) *ListNode {
   head1 := &ListNode{} // 存放小于x的链表
   head2 := &ListNode{} // 存放大于等于x的链表
   p1, p2 := head1, head2
   for head != nil {
      if head.Val < x {
         p1.Next = head
         p1 = p1.Next
      } else {
         p2.Next = head
         p2 = p2.Next
      }
      head = head.Next
   }
   p2.Next = nil
   // 连接两个链表
   p1.Next = head2.Next
   return head1.Next
}

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

解题思路：

假设链表有n个节点,那么倒数第k个节点,就是正数第n-k+1个节点

遍历一次链表,获取链表长度n,再重新遍历一次找到第n-k+1个节点即可

能不能遍历一次就搞定呢

首先我们定义一个指针p1,p1先走k步,那么他还需要走n-k步即可到达尾部

此时我们再申明一个指针p2,指向头部, p1和p2同时前进,当p1到达尾部时,p1正好走了n-k步,在n-k+1个节点上,就是倒数第k个节点

为了方便删除操作,申明p2时申明一个前置节点,按照上述步骤,p1到达末尾, p2到达倒数第n个节点的前置节点, 直接删除p2下一个节点即可

示例代码：

func removeNthFromEnd(head *ListNode, n int) *ListNode {
   p := &ListNode{0, head}
   p1, p2 := head, p
   for i := 0; i < n; i++ {
      p1 = p1.Next
   }

   for p1 != nil {
      p1 = p1.Next
      p2 = p2.Next
   }
   p2.Next = p2.Next.Next
   return p.Next
}

876. 链表的中间结点

解题思路：

要找到中间节点,常规的办法是遍历一遍,拿到链表的长度,再遍历一次得到n/2个节点,也就是中间节点

使用快慢指针的方式,申明两个指针,每当慢指针前进一步,快指针就前进两步,这当看指针走到链表末尾,慢指针刚好到链表的中间节点

当链表长度为偶数时,快指针走到指针末尾,而慢指针刚好走到两个中间节点靠后的那个节点,符合题意

示例代码：

func middleNode(head *ListNode) *ListNode {
   slow, fast := head, head
   for fast != nil && fast.Next != nil {
      slow = slow.Next
      fast = fast.Next.Next
   }
   return slow
}

160. 相交链表

解题思路：

需要判断两个链表是否有交点,其核心在于两个链表同时到达相交点c1

先让两个指针同时走到距离尾部相同的距离

然后依次往后遍历, 如果p1与p2相等,他们就走到了相交的节点,否则会走到链表尾部

示例代码：

func getIntersectionNode(headA, headB *ListNode) *ListNode {
   var lenA, lenB int
   for p := headA; p != nil; p = p.Next {
      lenA++
   }
   for p := headB; p != nil; p = p.Next {
      lenB++
   }
   p1, p2 := headA, headB
   if lenA > lenB {
      for i := 0; i < lenA-lenB; i++ {
         p1 = p1.Next
      }
   } else {
      for i := 0; i < lenB-lenA; i++ {
         p2 = p2.Next
      }
   }

   // 注意题意,提供的两个链表中存在相同链表,所以直接判断两个链表相等即可
   for p1 != p2 {
      p1 = p1.Next
      p2 = p2.Next
   }
   return p1
}

解题思路：

解题的核心依旧是如何同时到达相交节点c1

把两个链表收尾相连，这样两个链表的长度就一致了，即p1 = headA + headB, p2 = headB + headA

同事遍历两个链表，如果有相交点，他们会同时到达c1，否则会走向链表尾部

示例代码：

func getIntersectionNode(headA, headB *ListNode) *ListNode {
   p1, p2 := headA, headB
   for p1 != p2 {
      if p1 == nil {
         p1 = headB
      }
      if p2 == nil {
         p2 = headA
      }
      p1 = p1.Next
      p2 = p2.Next
   }
   return p1
}

141. 环形链表

解题思路：

定义快慢指针,慢指针每次走1步,快指针走两步

如果链表中存在环,那么快指针会追上慢指针,否则快指针会走到链表末尾

示例代码：

func hasCycle(head *ListNode) bool {
   slow, fast := head, head
   for fast != nil && fast.Next != nil {
      slow = slow.Next
      fast = fast.Next.Next
      if slow == fast {
         return true
      }
   }
   return false
}

142. 环形链表 II

解题思路：

假设快慢指针相遇，慢指针走了k步,那么快指针一定走了2k步，快指针多走的这k步就是在环里转圈圈,所以k的值就是环长度的整数倍

假设相遇点为m，那么环起点就为k-m，也就是说，从链表头部前进k-m就可以到达环起点

因为相遇点为m，k为环长度的倍数，所以只需要再走k-m步就可以到底环起点

所以当两个指针相遇时，重新定义一个指针从头出发，与慢指针再次相遇的地方就是环起点

示例代码：

func detectCycle(head *ListNode) *ListNode {
   slow, fast := head, head
   for fast != nil && fast.Next != nil {
      slow = slow.Next
      fast = fast.Next.Next
      if slow == fast {
         p := head
         for p != slow {
            p = p.Next
            slow = slow.Next
         }
         return p
      }
   }
   return nil
}

83. 删除排序链表中的重复元素

解题思路：

定义快慢指针，快指针fast在前面探路，slow跟在后面，找到一个不重复的元素时，将slow指向fast，完成元素的删除

此题与26思路一样，不同的是将数组的操作变成了链表

示例代码：

func deleteDuplicates(head *ListNode) *ListNode {
   if head == nil {
      return nil
   }
   slow, fast := head, head
   for fast != nil {
      if slow.Val != fast.Val {
         // nums[slow] = nums[fast]
         slow.Next = fast
         // slow ++
         slow = slow.Next
      }
      // fast ++
      fast = fast.Next
   }
   // 断开与后面重复元素的链接
   slow.Next = nil
   return head
}