代码随想录算法训练营|day4

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

文章详解

(1) 创建虚拟头节点
虚拟头节点指向node2，node2指向node1，node1指向下次翻转的首节点
移动虚拟头节点到下次翻转的首节点的前个节点，即node1

func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    dummy := &ListNode{
        Next : head,
    }
    cur := dummy
    for cur.Next != nil && cur.Next.Next != nil{
        tmp := cur.Next.Next.Next
        node1 := cur.Next
        node2 := cur.Next.Next
        cur.Next = node2
        node2.Next = node1
        node1.Next = tmp
        cur = node1
    }
    return dummy.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

(2) 递归

func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := head.Next
    // 将剩余节点两两交换后，新的头节点为head的Next节点
    head.Next = swapPairs(newHead.Next)
    newHead.Next = head
    return newHead
}
1
2
3
4
5
6
7
8
9
10

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

文章详解
(1) 按部就班：先计算链表长度，再删除对应节点

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    cur := head
    size := 1
    for cur.Next != nil{
        cur = cur.Next
        size++
    }
    if n > size{
        return head
    }
    // 设置虚拟头节点，不需要考虑head为空
    dummy := &ListNode{
        Next : head,
    }
    cur = dummy
    for i := 0; i < size - n ; i++ {
        cur = cur.Next
    }
    cur.Next = cur.Next.Next
    return dummy.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(2) 快慢指针：快慢指针相差n，快指针走到链表尾，慢指针指向待删除结点的前一个节点

func removeNthFromEnd(head *ListNode, n int) *ListNode {
       // 设置虚拟头节点，不需要考虑head为空
    dummy := &ListNode{
        Next : head,
    }
    fast, slow := dummy, dummy
    for i := 0; i < n; i++ {
        fast = fast.Next
    }
    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }
    slow.Next = slow.Next.Next
    return dummy.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(3) 栈

func removeNthFromEnd(head *ListNode, n int) *ListNode {
     nodes := []*ListNode{}
     dummy := &ListNode{
         Next : head,
     }
     cur := dummy
     for cur != nil {
         nodes = append(nodes, cur)
         cur = cur.Next
     }
     prev := nodes[len(nodes) - n - 1]
     prev.Next = prev.Next.Next
     return dummy.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

面试题：链表相交

文章详解
(1) 双指针：若相交，pa, pb 走完两条链表不相交的部分及相交部分找到第一个交点，若不相交，走完两条链表总长，返回nil

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    pa, pb := headA, headB
    for pa != pb {
        if pa == nil {
            pa = headB
        }else {
            pa = pa.Next
        }
        if pb == nil {
            pb = headA
        }else {
            pb = pb.Next
        }
    }
    return pa
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

(2) 哈希集合：集合存储的是节点地址
力扣题解

142.环形链表II

文章详解
(1) 快慢指针

func detectCycle(head *ListNode) *ListNode {
    fast, slow := head, head
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            tmp := head
            for tmp != slow {
                tmp = tmp.Next
                slow = slow.Next
            }
        return tmp
        }
    }
    return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(2) 哈希集合
力扣题解

总结

链表中，虚拟头节点很重要；找交点、指定节点进行操作，注意快慢指针的使用；递归~ 哈哈哈目前学不会了