【代码随想录】算法训练计划04

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

题目：

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

思路：

• 链表这种题目吧，画个图，问题就解决了一半了

• 另外一半就是注意条件，和需要什么变量

• 

// 代码一刷——虚拟头
 // 不要用反转链表的方法，要用本质的方法，模拟思考,注意需要什么变量
func swapPairs(head *ListNode) *ListNode {
    dummyHead := &ListNode{}
    dummyHead.Next = head
    cur := dummyHead
    for cur.Next != nil && cur.Next.Next != nil {
        next := cur.Next
        next2 := cur.Next.Next.Next
        cur.Next = cur.Next.Next
        cur.Next.Next = next
        next.Next = next2
        cur = cur.Next.Next
    }
    return dummyHead.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2、19. 删除链表的倒数第 N 个结点

题目：
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路：

• 双指针法，很有意思哈
• 快指针先走 n+1 步，接着快慢一起移动即可，注意循环条件
• 注意快慢指针初始值

func removeNthFromEnd(head *ListNode, n int) *ListNode {
    // 代码一刷，双指针
    dummy := &ListNode{Next:head}
    slow := dummy
    fast := dummy
    for i:=0; i<=n; i++ {
        fast = fast.Next
    }
    for fast != nil {
        slow = slow.Next
        fast = fast.Next
    }
    slow.Next = slow.Next.Next
    return dummy.Next
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3、面试题 02.07. 链表相交

题目：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：

思路：

• 带入试一试便知道
• 很神奇，一起走，走到nil，就换到另一个链表起始
• 或者也可用上一题的思路去解，快指针先走 n+1 步

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // 代码一刷——双指针
    l1, l2 := headA, headB
    for l1 != l2 {
        if l1 != nil {
            l1 = l1.Next
        } else {
            l1 = headB
        }

        if l2 != nil {
            l2 = l2.Next
        } else {
            l2 = headA
        }
    }
    return l2
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4、142.环形链表II

题目：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。

思路：

• 快慢指针+数学推理
• 首先知道，快慢指针，不只是说，快的在前边，也可以是速度是慢指针的 n 倍，这里是二倍
• 然后就是数学推理了，可以看卡尔的视频讲解
• 注意 slow 进入圈后，slow=fast了，然后是定义一个新的头节点位置，开始循环
  

func detectCycle(head *ListNode) *ListNode {
    // 代码一刷——双指针
    slow := head
    fast := head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            index1 := head
            index2 := slow
            for index1 != index2 {
                index1 = index1.Next
                index2 = index2.Next
            }
            return index1
        }
    }
    return nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19