链表的双指针算法#
876. 链表的中间结点#
给定一个单链表的头节点 head，返回链表的中间节点。
如果有两个中间节点，则返回第二个中间节点。
示例 1:
输入: head = [1,2,3,4,5]
输出: [3,4,5]
解释: 链表的中间节点是节点 3。
示例 2:
输入: head = [1,2,3,4,5,6]
输出: [4,5,6]
解释: 链表的中间节点是节点 4 和 5，返回第二个中间节点。
解法#
根据例子，看起来是获取链表中间位置到末尾的节点，这与双指针有什么关系呢？看到给出的代码，明白了，不是数组，给出的是一个 ListNode。
定义的代码如下:
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func middleNode(_ head: ListNode?) -> ListNode? {
}
}
一开始没理解给出的 ListNode 和上面的示例中的 head 是如何对应起来的。
经过一段时间的思考，我明白了，
链表
1 -> 2 -> 3 -> 4 -> 5
val 1
next 2
val 2
next 3
val 3
next 4
val 4
next 5
val 5
next nil
理解了 ListNode 之后，那如何获取中间的 ListNode 呢？
定义两个变量，s 和 f，每次循环 s 指向下一个元素，而 f 指向下下个元素，这样最后 f 结束时，s 指向的就是中间。
/*
最开始
f
1 -> 2 -> 3 -> 4 -> 5
s
第一次循环
f
1 -> 2 -> 3 -> 4 -> 5
s
第二次循环
f
1 -> 2 -> 3 -> 4 -> 5
s
第三次循环
当 f 的 next 为空时结束，此时 s 指向的是中间
f = fast pointer
s = slow pointer
*/
最终代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func middleNode(_ head: ListNode?) -> ListNode? {
var slow = head
var fast = head
while (fast != nil) && (fast?.next != nil) {
slow = slow?.next
fast = fast?.next?.next
}
return slow
}
}
19. 删除链表的倒数第 N 个结点#
给定一个链表的头节点 head，删除链表的倒数第 n 个节点，并返回链表的头节点。
示例 1:
输入: head = [1,2,3,4,5], n = 2
输出: [1,2,3,5]
示例 2:
输入: head = [1], n = 1
输出: []
示例 3:
输入: head = [1,2], n = 1
输出: [1]
解法#
这个地方，需要注意的是 "倒数第 n 个结点"，是从末尾数第几个。
我的想法是首先获取整个链表的长度，然后整个长度减去 (n - 1)，就是正着数的第几个节点，从 1 开始计数，然后赋值，从头开始赋值，如果刚好到这个位置，则跳过。
但是使用双指针的算法是，定义 slow 和 fast，然后先让 fast 向前走 n 步，再让 slow 和 fast 一起向前走，这样当 fast 走到尾部时，slow 刚好指向要移除的节点，然后跳过这个节点赋值。
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
let node = ListNode(0, head)
var slow: ListNode? = node
var fast: ListNode? = node
var m = n
while m > 0 {
fast = fast?.next
m -= 1
}
while fast?.next != nil {
slow = slow?.next
fast = fast?.next
}
slow?.next = slow?.next?.next
return node.next
}
}