两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
T1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_head = ListNode(next=head)
        current = dummy_head
        while current.next and current.next.next: #注意先后顺序防止空指针异常
            temp1 = current.next
            temp2 = temp1.next.next
            current.next = current.next.next
            current.next.next = temp1
            temp1.next = temp2
            current = current.next.next
        return dummy_head.next

有点像昨天的反转列表，也采用了temp指针来保存数据，这道题核心在与两两交换前需要先找到前置节点，并且在循环判断的条件中要注意先后顺序防止空指针异常，当然指针确实有点绕，画个图还是很有帮助的。

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
T2

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
示例 2：
输入：head = [1], n = 1 输出：[]
示例 3：
输入：head = [1,2], n = 1 输出：[1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy_head = ListNode(next=head)
        slow = dummy_head
        fast = dummy_head
        n += 1
        while n and fast :
            n -= 1
            fast = fast.next 
        while fast:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy_head.next

这道题就是快慢指针，要想找到倒数第二个n，那就先让fast指针移动n+1步，然后再让slow指针和fast指针同时移动，直到fast指针指向None，这时候slow指针就指向了倒数第二个n前一个的位置。只有找到倒二的前一个位置，才能进行删除操作。

链表相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
T3-1
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构
T3-2
T3-3

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
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        count1 = 0
        count2 = 0
        cur1 = headA
        cur2 = headB
        while cur1 :
            count1 += 1
            cur1 = cur1.next
        cur1 = headA
        while cur2:
            count2 += 1
            cur2 = cur2.next
        cur2 = headB
        less = count1 - count2
        if less > 0:
            for i in range(less):
                cur1 = cur1.next
            while cur1 != cur2:
                cur1 = cur1.next
                cur2 = cur2.next
            return cur1
        else :
            less = -less
            for i in range(less):
                cur2 = cur2.next
            while cur1 != cur2:
                cur1 = cur1.next
                cur2 = cur2.next
            return cur2

这是我一开始的想法，先找到两个链表的长度，然后让长的链表先移动长度差的步数，然后再让两个链表同时移动，直到找到相交的节点。
实际上我找了非常有意思的解法，就是让两个链表同时移动，当其中一个链表到达末尾时，让它指向另一个链表的头节点，然后继续移动，当两个链表相交时，它们会在相交点相遇。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if not headA or not headB:
            return None
        cura = headA
        curb = headB
        while cura != curb:
            cura = cura.next if cura else headB
            curb = curb.next if curb else headA
        return cura

一种类似算梯形面积的方法，把短的和长的拼在一起，简单来说，就是我让两条链表同时移动，当其中一个链表到达末尾时，让它指向另一个链表的头节点，然后继续移动，当两个链表相交时，它们会在相交点相遇。（感觉这么说有点抽象），那就假设相同部分长度c，不相同部分长的a，短的b。第一条先走a+c，第二条走b+c，此时让一再走b，二再走a，这时候两条都是a+b+c，欸刚好到相同长度，并且接下来走的是相同的部分
别笑我

环形链表II

题意： 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表
T4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                index = slow
                index_s = head
                while index != index_s:
                    index = index.next
                    index_s = index_s.next
                return index
        return None

还是快慢指针，快指针每次移动两步，慢指针每次移动一步，当它们相遇时，说明链表有环。（因为不是环肯定不会相遇，快指针早就跑远了）
这时候就是判断环的入口了，让一个指针从相遇点开始移动，另一个指针从链表头开始移动，当它们相遇时，就是环的入口。（数学：假设head到环入口是a，环入口到相遇点是b，相遇点到环入口是c，那么快指针走的距离是a+b+n（b+c），慢指针走的距离是a+b，因为快指针每次移动两步，慢指针每次移动一步，所以快指针走的距离是慢指针的两倍，即2(a+b) = a+b+n（b+c），所以a = （n-1）（b+c）+c，b+c就是一圈，转一圈也会回到起点，所以两个指针再次出发就会在入口相遇）
但，实际上不需要index，在python里面直接让慢指针回到起点，然后快指针再相遇的位置继续走，速度和慢指针相同，当它们再次相遇时，就是环的入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow == fast:
                fast = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return fast
        return None