5.4 双指针秒杀链表问题

双指针秒杀链表问题 #

相比于双指针秒杀数组问题来说，双指针秒杀链表问题更有技巧性。比如说，经常会定义虚拟头结点dummy，因为可能会涉及到删除head节点这类题目。

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

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    slow, fast := head, head
    for fast != nil {
        if fast.Val != slow.Val {
            slow = slow.Next
            slow.Val = fast.Val
        }
        fast = fast.Next
    }
    slow.Next = nil
    return head
}
//           f
//     s
// 1 1 2 3 3
// 1 2 2 3 3
// 1 2 3 3 3

876.链表的中间结点 #

传送门

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

140.训练计划II(剑指Offer) #

传送门

func trainingPlan(head *ListNode, cnt int) *ListNode {
    if head == nil {
        return nil
    }
    slow, fast := head, head
    for i:=0; i<cnt; i++ {
        fast = fast.Next
    }
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
    return slow
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func partition(head *ListNode, x int) *ListNode {
    if head == nil {
        return nil
    }
    dummy1 := &ListNode{-1,nil}
    dummy2 := &ListNode{-1,nil}
    cur1 := dummy1
    cur2 := dummy2

    for head != nil {
        if head.Val < x {
            cur1.Next = head
            cur1 = cur1.Next            
        }else {
            cur2.Next = head
            cur2 = cur2.Next
        }
        // head = head.Next // 这样写最后链表可能成环。5 - > 2，当前head在5，head往下挪后，还有指针指向了2，最后将两个链表连接成一个链表时，可能会形成环。所以需要将next指针置空，下面3行，可简写为一行 // head, head.Next = head.Next, nil
        tmp := head.Next
        head.Next = nil
        head = tmp
    }

    cur1.Next = dummy2.Next
    return dummy1.Next
}