代码随想录算法训练营第四天 | 24、19、160、142

算法
, , ,

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
package main

func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    prev := dummy
    current := dummy.Next

    for current != nil && current.Next != nil {
        nextNode := current.Next
        // 交换相邻节点
        prev.Next = nextNode
        current.Next = nextNode.Next
        nextNode.Next = current
        // 更新指针以处理下一对节点
        prev = current
        current = current.Next
    }

    return dummy.Next
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
package main

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{Next: head} // 创建虚拟头节点简化头节点删除逻辑
    slow, fast := dummy, dummy

    // 快指针先移动 n 步
    for i := 0; i < n; i++ {
        fast = fast.Next
    }

    // 同时移动快慢指针直到快指针到达最后一个节点
    for fast.Next != nil {
        slow = slow.Next
        fast = fast.Next
    }

    // 删除目标节点
    slow.Next = slow.Next.Next
    return dummy.Next
}

160. 链表相交

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
package main

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    pA, pB := headA, headB

    // 当两个指针未相遇时继续遍历
    for pA != pB {
        // 如果 pA 到达末尾，则转向 headB 继续遍历；否则继续前移
        if pA == nil {
            pA = headB
        } else {
            pA = pA.Next
        }

        // 同理处理 pB
        if pB == nil {
            pB = headA
        } else {
            pB = pB.Next
        }
    }
    // 返回相遇点（包括 nil）
    return pA
}

142. 环形链表 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
package main

func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }

    slow, fast := head, head
    // 第一阶段：检测环是否存在
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            break // 相遇点
        }
    }

    // 无环情况
    if fast == nil || fast.Next == nil {
        return nil
    }

    // 第二阶段：寻找环入口
    slow = head // 重置慢指针到起点
    for slow != fast {
        slow = slow.Next
        fast = fast.Next // 快指针改为每次走一步
    }
    return slow
}