24. 两两交换链表中的节点 搞清楚基本单元: 两个Node, 记得保存before

https://leetcode.cn/problems/swap-nodes-in-pairs

解题思路

搞清楚基本单元: 两个Node
记得保存before
注意循环条件

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0,head)
        before = dummy
        i = head

        while i and i.next:
            # 交换
            j = i.next # i,j为一组
            tmp = j.next
            before.next = j
            i.next = tmp
            j.next = i
            # 下一组
            before = i
            i = i.next
        
        return dummy.next

19.删除链表的倒数第N个节点 先计数,后正着数

解题思路

我采用了最简单的思路, 先计数, 后正着数

代码

# 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]:
        # 一个很简单的思路
        # count总共多少nodes, count-n+1为正着数第i个
        dummy = ListNode(0,head)
        cur = dummy
        count = 0
        
        # step1: 总共多少nodes
        while cur.next:
            count += 1
            cur = cur.next

        # step2: 正着数, 找到它的前一个
        cur = dummy
        for i in range(count-n):
            cur = cur.next
        cur.next = cur.next.next

        return dummy.next

面试题 02.07. 链表相交 把长的截断使得两者一样长

解题思路

一个很简单的思路
step1: 计算A,B的nodes的个数cnt_a,cnt_b
step2: 假设A长一点, 用cnt_a - cnt_b, 即让两者长度相等且tail相同, 然后A和B同时开始从新的开头开始数; 跳出的条件为指针一样

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # 一个很简单的思路
        # step1: 计算A,B的nodes的个数cnt_a,cnt_b
        # step2: 假设A长一点, 用cnt_a - cnt_b, 即让两者长度相等且tail相同, 然后A和B同时开始从新的开头开始数; 跳出的条件为指针一样

        cnt_a = 0
        cnt_b = 0
        dummy_a = ListNode(0)
        dummy_b = ListNode(0)
        dummy_a.next = headA
        dummy_b.next = headB

        cur_a = dummy_a
        cur_b = dummy_b

        # step1: 计算A,B的nodes的个数cnt_a,cnt_b
        while cur_a.next:
            cur_a = cur_a.next
            cnt_a += 1
        while cur_b.next:
            cur_b = cur_b.next
            cnt_b += 1

        # print("cnt_a = ",cnt_a)
        # print("cnt_b = ",cnt_b)
        
        # step2:
        # 让A是大的
        if cnt_a < cnt_b:
            tmp = headA
            headA = headB
            headB = tmp
            tmp = cnt_a
            cnt_a = cnt_b
            cnt_b = tmp
            tmp = dummy_a
            dummy_a = dummy_b
            dummy_b = tmp
        # print()
        # print("let A longer:")
        # print("headA = ",headA)
        # print("headB = ",headB)
        # 把A"截断"
        cur_a = dummy_a
        for i in range(cnt_a - cnt_b):
            cur_a = cur_a.next
            # print("cut off")
        dummy_a = cur_a
        # print("after cut off:")
        # print("dummy_a = ",dummy_a)
        # print("dummy_b = ",dummy_b)
        # 开始AB同时向后
        cur_a = dummy_a
        cur_b = dummy_b
        while cur_a and cur_a != cur_b:
            cur_a = cur_a.next
            cur_b = cur_b.next
        if cur_a == None:
            return None
        else:
            return cur_a

142.环形链表II 搞明白循环

Problem: 142. 环形链表 II

Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        s = f = head
        while f and f.next:
            s = s.next
            f = f.next.next
            # 相遇 => 存在环
            # 找入环点
            if s == f:
                f = head
                while f != s:
                    f = f.next
                    s = s.next
                return f
        return None