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

• [x] 没啥技巧，画图就行

func swapPairs(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    virHead := ListNode{Next: head}
    p1 := &virHead
    p2 := head

    for p2 != nil && p2.Next != nil {
        p1.Next = p2.Next
        p1 = p2.Next
        p2.Next = p1.Next
        p1.Next = p2

        p1 = p1.Next
        p2 = p2.Next
    }

    return virHead.Next
}

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

• [x] 画个图，快慢指针，让p1和p2保持固定距离即可

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    virHead := &ListNode{Next: head}
    p1 := virHead
    p2 := virHead
    //先让p2后移n次，然后同步后移得出p1
    for i := 0; i < n; i++ {
        p2 = p2.Next
    }
    // p1与p2一同移动，p2移动到末尾
    for p2.Next != nil {
        p2 = p2.Next
        p1 = p1.Next
    }

    // 删除p1.Next节点
    temp := p1.Next
    p1.Next = temp.Next
    // free(temp)
    return virHead.Next  
}

面试题 02.07. 链表相交

• [x] 快慢指针

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getLen(head *ListNode) int{
    i := 0
    p := head
    for p != nil {
        p = p.Next
        i++
    }
    return i
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    la := getLen(headA)
    lb := getLen(headB)
    for i := 0; i < la - lb; i++ {
        headA = headA.Next
    }
    for i := 0; i < lb - la; i++ {
        headB = headB.Next
    } 

    for headA != nil && headB != nil {
        if headA == headB {
            return headA
        }
        headA = headA.Next
        headB = headB.Next
    }
    return nil

}

• [x] 哈希表

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    mp := make(map[*ListNode]bool)
    for headA != nil {
        mp[headA] = true
        headA = headA.Next
    }
    for headB != nil {
        if _, ok := mp[headB]; ok { // 已经存在了相同节点
            return headB
        }
        mp[headB] = true
        headB = headB.Next
    }
    return nil
}

142.环形链表II

• [x] 快慢指针

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

• [ ] 哈希（略）

---

• 分类： 算法
• 标签： 算法基础 链表 快慢指针