初级算法-链表

知识

链表是一种线性数据结构。

查找O(n)，删除O(1)，插入O(1)，随机读取O(n)。

技巧

节点关系：

对于链表来说，我们通常没有办法知晓链表的全貌，只能了解从已知的当前节点开始的表的内容。所以，在对链表问题做处理时，考虑节点之间的关系（主要是当前节点相关的函数关系）是解决链表问题的主要手段。

所以，在进行链表题时，预先将整个链表的处理流程书写完毕再写代码有事半功倍的效果。

表头设置（浅拷贝）：

由于链表通常需要使用对象的next方法来获取下一节点，所以为了在处理完整个链表后，可以对初始节点进行返回，对表头节点进行浅拷贝是非常有用的。

在这里需要注意，对next节点的继承需要在当前节点处理之前，不然会因为浅拷贝而改变next节点的状态。

此外需要注意，随着对head的迭代或者递归，直接指定表头节点的next为head是无效的手段。

迭代或递归：

双指针法：

重点看反转链表一题。

练习

237. 删除链表中的节点

问题：

https://leetcode-cn.com/problems/delete-node-in-a-linked-list/

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

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

示例 1：

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

示例 2：

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

提示：

链表中节点的数目范围是 [2, 1000]
-1000 <= Node.val <= 1000
链表中每个节点的值都是 唯一 的
需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

解答：

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

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        # 将下一个节点拉到当前的位置来
        if node.next: 
            node.val = node.next.val
            node.next = node.next.next
        else: node.val = None

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

问题：

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

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

示例 1：

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

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

解答：

# 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:
        k = []
        while head.next != None:
            k.append(head)
            head = head.next
        k.append(head)
        if n == len(k):
            if len(k)>=2:
                return k[1]
            else: return None
        elif n-1 <= len(k) and n+1 <= len(k):
            if k[-n-1] != k[-n+1] and n != 1:
                k[-n-1].next = k[-n+1]
            else: 
                k[-n-1].next = None
        elif n+1 <= len(k):
            k[-n-1].next = None
        else:
            return None
        return k[0]

但是，以上代码还是在模拟题目的表层模式，如果想要写的更加简单，应该思考如何从表层模式过渡到深层模式。

206. 反转链表

问题：

https://leetcode-cn.com/problems/reverse-linked-list/

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

示例 1：

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

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解答：

# 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 not head: return head
        elif not head.next: return head
        else:
            pre = None
            cur = ListNode(None)
            cur = head
            # 迭代
            while cur:
                # 继承next
                tmp = cur.next
                # 开始处理
                cur.next = pre 
                # 进位
                pre = cur
                cur = tmp
            return pre
	def reverseList(self, head: ListNode) -> ListNode:
        if not head: return head
        elif not head.next: return head
        else:
            pre = None
            cur = ListNode(None)
            cur = head
            # 迭代
            while cur:
                # 继承next
                tmp = cur.next
                # 开始处理
                cur.next = pre 
                # 进位
                pre = cur
                cur = tmp
            return pre

21. 合并两个有序链表

问题：

https://leetcode-cn.com/problems/merge-two-sorted-lists/

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

解答：

# 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]:
        if not list1: return list2
        if not list2: return list1
        head = ListNode()
        cur = head
        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return head.next

234. 回文链表

问题：

https://leetcode-cn.com/problems/palindrome-linked-list/

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

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 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 isPalindrome(self, head: ListNode) -> bool:
        k = []
        if head.next == None:
            return True
        while head != None:
            k.append(head.val)
            head = head.next
        if k == []:
            return True
        elif len(k) != 1:
            i = 0
            while i < len(k)//2:
                if k[i] != k[-i-1]:
                    return False
                else:
                    i += 1
            return True
        else: return False

141. 环形链表

问题：

https://leetcode-cn.com/problems/linked-list-cycle/

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

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

如果链表中存在环，则返回 true 。否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

解答：

# 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:
        k = []
        for i in range(10**4):
            if head == None:
                return False
            elif head.next == None:
                return False
            elif head not in k:
                k.append(head)
                head = head.next
            else:
                return True
        return False

上面的方法很慢，更好的方法是使用变速双指针。

# 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:

Whiteloran's Blog

Leetcode 初级算法-链表

初级算法-链表

知识

技巧

节点关系：

表头设置（浅拷贝）：

迭代或递归：

双指针法：

练习

237. 删除链表中的节点

问题：

解答：

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

问题：

解答：

206. 反转链表

问题：

解答：

21. 合并两个有序链表

问题：

解答：

234. 回文链表

问题：

解答：

141. 环形链表

问题：

解答：