链表—Python_python listnode

---

2. 两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头
示例：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode(0)
        p = dummy
        carry = 0
        while l1 or l2:
            if l1 and l2:
                value = l1.val + l2.val + carry
            elif l1:
                value = l1.val + carry
            elif l2:
                value = l2.val + carry
            carry = 1 if value > 9 else 0
            value = value - 10 if value > 9 else value
            p.next = ListNode(value)
            p = p.next
            l1 = l1.next if l1 else l1
            l2 = l2.next if l2 else l2
        if carry == 1:
            p.next = ListNode(1)
        return dummy.next
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

复杂度分析

时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。

空间复杂度：O(1)。

21. 合并两个有序链表

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

• 方法一(迭代)：时间复杂度O(n+m)，空间复杂度O(1)

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

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode(-1)
        p = head
        while list1 and list2:
            if list1.val <= list2.val:
                p.next = list1
                list1 = list1.next
            else:
                p.next = list2
                list2 = list2.next
            p = p.next

        p.next = list1 if list1 != None else list2
        return head.next             
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 方法二(递归)：时间复杂度O(n+m)，空间复杂度O(n+m)

class Solution():
    def mergeTwoLists(self,list1,list2):
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2
1
2
3
4
5
6
7
8
9
10
11
12
'
运行
运行

---

23. 合并K个升序链表

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

• heapq 实现的优先级队列

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

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        import heapq
        dummy = ListNode(0)
        p = dummy
        head = []
        for i in range(len(lists)):
            if lists[i] :
                heapq.heappush(head, (lists[i].val, i))
                lists[i] = lists[i].next
        while head:
            val, idx = heapq.heappop(head)
            p.next = ListNode(val)
            p = p.next
            if lists[idx]:
                heapq.heappush(head, (lists[idx].val, idx))
                lists[idx] = lists[idx].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
22
23
24

时间复杂度：优先队列 pq 中的元素个数最多是 k，所以一次 pop 或者 push 方法的时间复杂度是 O(logk)；所有的链表节点都会被加入和弹出 pq，这里最多有 $kn$ 个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为 $O(kn\times \log k)$。

空间复杂度：优先队列中的元素不超过 $k$个，故渐进空间复杂度为 $O(k)$。

---

剑指 Offer 22. 链表中倒数第k个节点

剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

• 时间复杂度 O(N)

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

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        p1 = head
        for i in range(k):
            p1 = p1.next
        p2 = head
        while p1:
            p1 = p1.next
            p2 = p2.next
        return p2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

面试题 02.02. 返回倒数第 k 个节点

面试题 02.02. 返回倒数第 k 个节点

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：与上题思路一致，只是函数返回的第k个节点的值，其他全部一样

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

class Solution:
    def kthToLast(self, head: ListNode, k: int) -> int:
        # 指针 p1 指向链表的头节点 head
        p1 = head
        for i in range(k):
            p1 = p1.next
        p2 = head
        while p1:
            p1 = p1.next
            p2 = p2.next
        return p2.val
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

剑指 Offer 18. 删除链表指定值的节点

剑指 Offer 18. 删除链表指定值的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

示例 :

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
1
2
3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode()
        p = dummy
        while head.val != val:
            p.next = head
            head = head.next
            p = p.next
        p.next = head.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

237. 删除链表中的指定节点

237. 删除链表中的指定节点

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9
1
2
3

• 思路：和下一个节点交换，再删除下一个节点
• 时间复杂度：O(1)，空间复杂度：O(1)，主要的代码就两行。

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

class Solution:
    def deleteNode(self, node: ListNode):
        """
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next
1
2
3
4
5
6
7
8
9
10
11
12
13

---

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

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

给你一个链表，删除链表的倒数第 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: ListNode, n: int) -> ListNode:
        dummy = ListNode(0,head)
        p1 = head
        for i in range(n):
            p1 = p1.next
        p2 = dummy
        while p1:
            p1 = p1.next
            p2 = p2.next
        p2.next = p2.next.next
        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

复杂度分析

时间复杂度：O(N)，其中 N为链表的长度。

空间复杂度：O(1)。

---

876. 链表的中间结点

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

• 思路：

如果想一次遍历就得到中间节点，可以使用「快慢指针」。两个指针 slow 和 fast 分别指向链表头结点 head。每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = head
        slow = head
        while fast and fast.next: # 两个条件
            fast = fast.next.next
            slow = slow.next 
        return slow
1
2
3
4
5
6
7
8

---

2095. 删除链表的中间节点

2095. 删除链表的中间节点

给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head.next == None:
            return
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            pre = slow
            slow = slow.next
        
        pre.next = slow.next
        return head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

面试题 02.01. 移除重复节点

面试题 02.01. 移除重复节点

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

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

class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        
        dummy = ListNode(0,head)
        pre = dummy
        p = head
        memo = []
        while p:
            if p.val in memo:
                p = p.next
                pre.next = p
            else:
                memo.append(p.val)
                p = p.next
                pre = pre.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
22
23
24
25

---

141. 环形链表

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

• 解决方案同求链表的中间节点也是使用快慢指针：

每当慢指针 slow 前进一步，快指针 fast 就前进两步。如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。

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

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

---

142. 环形链表 II

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        fast = head
        slow = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                break
        if fast == None or fast.next == None:
            return None

        slow = head
        while slow != fast:
            fast = fast.next
            slow = slow.next
        return slow
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

---

160. 相交链表

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

题目数据 保证 整个链式结构中不存在环。

• 思路：

可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：

# 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:
        p1 = headA
        p2 = headB
        while p1 != p2:
            if p1 == None:
                p1 = headB
            else:
                p1 = p1.next
                
            if p2 == None:
                p2 = headA
            else:
                p2 = p2.next
        return p1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

206. 反转链表

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

方法一：递归反转链表

• 递归函数的定义：输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点
• 时间复杂度：O(n)，其中 n是链表的长度；空间复杂度：O(n)。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head
        
        last = self.reverseList(head.next)
        head.next.next = head
        head.next = Non
        return last
1
2
3
4
5
6
7
8
9
10
11
12
13
14

方法二：迭代反转链表

• 时间复杂度：O(n)，其中 n是链表的长度；空间复杂度：O(1)。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None or head.next == None:
            return head

        p = head
        # 反转后尾节点的next为None
        dummy = None 
        while p:
            curr = p.next
            p.next = dummy
            dummy = p
            p = curr
        return dummy
1
2
3
4
5
6
7
8
9
10
11
12
13
14

反转链表前N个节点

def reverseN(head, n):
        if n == 1:
            return head   
        dummy = None
        pre = head
        p = head
        for i in range(n):
            curr = p.next
            p.next = dummy
            dummy = p
            p = curr

        pre.next = p
        return dummy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
'
运行
运行

---

92. 反转链表 II

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

方法一：递归

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        if left == 1:
            return self.reverseN(head,right)
        head.next = self.reverseBetween(head.next,left-1,right-1)
        return head
    
    def reverseN(self, head, n):
        if n == 1:
            return head   
        dummy = None
        pre = head
        p = head
        for i in range(n):
            curr = p.next
            p.next = dummy
            dummy = p
            p = curr

        pre.next = p
        return dummy
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

方法二：「穿针引线」反转链表（头插法）

• 时间复杂度：O(N)，其中 N 是链表总节点数。
• 空间复杂度：O(1)

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        dummy = ListNode()
        dummy.next = head
        pre = dummy
        for i in range(1,left):
            pre = pre.next

        p = pre.next
        for _ in range(right - left):
            curr = p.next
            p.next = curr.next
            curr.next = pre.next # 注意此处不能写 curr.next = p         
            pre.next = curr

        return dummy.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

25. K 个一组翻转链表

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
1
2

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        p1 = head
        p2 = head
        for i in range(k):
            if p1:
                p1 = p1.next
            else:
                return head
        newHead = self.reverseN(head,k)
        p2.next = self.reverseKGroup(p1, k)# 反转后p2是前k个节点的尾节点

        return newHead
    
    def reverseN(self, head, n):
        if n == 1:
            return head
        dummy = None
        p = head
        pre = head
        for i in range(n):
            curr = p.next
            p.next = dummy
            dummy = p
            p = curr

        pre.next = p
        return dummy
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

复杂度分析

• 时间复杂度：O(N)，其中 N 是链表总节点数。
• 空间复杂度：O(1)

---

1721. 交换链表中的节点

1721. 交换链表中的节点

给你链表的头节点 head 和一个整数 k 。

交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head == None or head.next == None:
            return head
        p1 = head
        for i in range(1,k):
            p1 = p1.next
        curr = p1
        val1 = curr.val
        p2 = head
        while p1.next:
            p1 = p1.next
            p2 = p2.next
        val2 = p2.val

        p2.val = val1
        curr.val = val2
        return head

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

---

234. 回文链表

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

方法一：把原始链表反转存入一条新的链表，然后比较这两条链表是否相同。

• 时间复杂度：O(N)，其中 N 是链表总节点数；空间复杂度：O(N)。

方法二：借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表。实际上就是把链表节点放入一个栈，然后再拿出来，这时候元素顺序就是反的

• 时间复杂度：O(N)，空间复杂度：O(N)。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        self.left = head
        return self.traverse(head)

    def traverse(self, head):
        if head == None:
            return True
        
        res = self.traverse(head.next)
        res = (res and self.left.val == head.val)
        self.left = self.left.next
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

方法三：优化空间复杂度

时间复杂度：O(N)，空间复杂度：O(1)。

思路：

1、先通过快慢指针来找到链表的中点

2、如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步

3、从slow开始反转后面的链表，再比较中点左右是否相同就可以了

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head == None or head.next == None:
            return True
        fast = head
        slow = head
        left =head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        if fast:
            slow = slow.next

        right = self.converse(slow)
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

    def converse(self,head):
        if head == None or head.next == None:
            return head

        dummy = None
        p = head
        while p:
            curr = p.next
            p.next = dummy
            dummy = p 
            p = curr
        return dummy
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