【代码随想录】链表

来源：爱玩科技网

1. 链表理论基础

什么是链表：链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。

链表的入口节点称为链表的头结点也就是head。
链表的类型：单链表、双链表、循环链表（解决约瑟夫环问题）。

链表的定义：

class ListNode:
	def __init__(self, val=0, next=None):
		self.val = val
		self.next = next

链表的增添和删除都是O(1)操作，也不会影响到其他节点。
性能分析

2. 移除链表元素

链表操作的两种方式：

直接使用原来的链表来进行删除操作。
- 普通结点如何移除：让节点next指针直接指向下下一个节点就可以了
- 头结点如何移除呢，其实只要将头结点向后移动一位就可以，这样就从链表中移除了一个头结点。
这种情况在单链表中移除头结点和移除其他节点的操作方式是不一样，其实在写代码的时候也会发现，需要单独写一段逻辑来处理移除头结点的情况。

设置一个虚拟头结点在进行删除操作

这样原链表的所有节点就都可以按照统一的方式进行移除了。

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # 创建虚拟头部节点以简化删除过程
        dummy = ListNode(next=head)

        # 遍历列表并删除值为val的节点
        current = dummy
        while current.next:
            if current.next.val == val:
                current.next = current.next.next   # 已经进行到下一步了
            else:
                current = current.next
        
        return dummy.next

707. 设计链表

获取第n个节点的值

在头部插入新节点

正确插入顺序是先让newnode.next = dummy_head.next，再让dummy_head.next = newnode，也就是先接再拆，而不是先拆后接会找不到后面的节点了。
写成self.dummy_head.next = ListNode(val, self.dummy_head.next)，非常强，很简洁

在第n个节点前插入新节点

仍然让current = head，那么n就是current.next，这样才能在n节点前插入新节点。
这里和获取第n个节点值不同的是：获取第n个节点值中current = dummy_head.next，n就是current；而这里current = dummy_head，n是current.next，其实就是current初始位置差一位的问题，原理上是一样的。
为什么要让current.next = n: 要在n前面插入节点，就要知道n前面一个节点的定位，所以要让current等于n前面的一个节点

删除第n个节点

要想删除第n个节点，要确定第n-1个节点，方便经典的做法是让current = n-1，这样current.next就是节点n，便于对current操作。
验证边界条件没有问题：假设删除第0个节点，current = dummy_head，那么current.next就是head，即第0个节点。

在尾部插入节点

则当前节点current要是尾部最后一个节点，而不是null
在尾部添加新节点后，默认后面就是null，不需要更改

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList:

    def __init__(self):
        self.dummy_head = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        # 判断边界条件
        if index < 0 or index >= self.size:   # index=self.size是越界的情况
            return -1
        
        # 遍历前index个结点
        current = self.dummy_head.next        # 起始遍历结点应该为self.dummy_head.next
        for i in range(index):
            current = current.next
        
        return current.val

    def addAtHead(self, val: int) -> None:
        self.dummy_head.next = ListNode(val, self.dummy_head.next)   # 解决了后续结点的问题
        self.size += 1

    def addAtTail(self, val: int) -> None:
        # 找到尾部结点
        current = self.dummy_head
        while current.next:
            current = current.next
        current.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        # 判断index边界条件
        if index < 0 or index > self.size:       # 这里不用考虑index=self.size是越界的情况
            return
        
        # 遍历找到index结点
        current = self.dummy_head
        for _ in range(index):
            current = current.next
        current.next = ListNode(val, current.next)
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        # 判断index边界条件
        if index < 0 or index >= self.size:       # index=self.size是越界的情况
            return
        
        # 遍历找到index结点
        current = self.dummy_head
        for _ in range(index):
            current = current.next
        current.next = current.next.next
        self.size -= 1


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

注意：

在 get 和 deleteAtIndex 方法中，将边界条件 index > self.size 改为 index >= self.size。start方法不需要这样
修正了 get 方法的遍历起始节点为 self.dummy_head.next，这样能够跳过虚拟头节点。

时间复杂度: 涉及 index 的相关操作为 $O (in d e x)$ , 其余为 $O (1)$
空间复杂度: $O (n)$

206.反转链表

是考察基础知识的很重要一环。
其实只需要改变链表的next指针的指向，直接将链表反转，而不用重新定义一个新的链表，如图所示:

# 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: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head

        while cur:           # 为什么是cur不是cur.next？
            tmp = cur.next    # 先把cur.next保存下来
            cur.next = pre    # 反转操作
            # 更新pre和cur指针
            pre = cur
            cur = tmp
        
        return pre

pythonic写法：

# 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: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head

        while cur:           
            cur.next, pre, cur = pre, cur, cur.next       # 这个顺序有什么讲究吗？
        
        return pre

疑问：

为什么是 while cur不是cur.next？
cur.next, pre, cur = pre, cur, cur.next 这个顺序有什么讲究吗？

双指针写法

没有用虚拟头节点
current = head, pre = null. 这样在反转的时候尾结点的后面指向的才是null.
何时遍历结束：当current指向空指针的时候，遍历的操作结束，之后不再需要其他操作。不然会出现空指针异常或者死循环。
用一个临时指针temp提前将current.next保存下来，这样就不会改变方向的时候找不到后一个节点了。

递归写法

是从双指针写法来的，先掌握好双指针写法。

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

current指向dummy head的时候，才能对节点1和2进行操作，同理，current指向2的时候，对节点3和4进行操作
遍历终止条件：对奇数个节点来说，current.next.next = null; 对偶数个节点来说，current.next = null——while(current.next != null) && (current.next.next = !null)。current.next != null要写在current.next.next != null前面，不然可能会发生空指针异常，因为万一current.next为空，就变成对空指针取值了
链表头节点：dummy_head.next
- 交换链表：
  temp = current.next 保存
  temp1 = current.next.next.next 保存
  - current.next = temp.next
  - current.next.next = temp #节点2已经变成current.next了，注意赋值变化的情况，不要写错了
  - temp.next = temp1
- 移动指针：current = current.next.next直接往后移两位
return的头节点应该是dummy_head.next

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

使用虚拟头节点，操作时无需判断是否是头节点
操作指针要指向要删除节点的前一个节点，才能达到要删除的目的。
快指针要走n步，多走一步，这样慢指针才会到要删除节点的前一个节点，达到删除的目的。⚠️注意，这里和随想录给的代码不一样的地方在于，如果判断fast.next也不为空，fast就要走n步，否则是走n+1步。

160.相交链表

改为复习之前刷过的labuladong相交链表题
等比例法
p1 指向 A 链表头结点，p2 指向 B 链表头结点
p1 走一步，如果走到 A 链表末尾，转到 B 链表
p2 走一步，如果走到 B 链表末尾，转到 A 链表
如果相交，指针将位于交点节点，如果没有交点，值为None
注意p1 = p1.next if p1 else p1 = headB这样写是不对的，应该是else headB

142. 环形链表 II

快指针相对于慢指针每次走一个节点，所以快指针一定可以从后面追上慢指针
慢指针一定是在第一圈被追上，代码随想录里面有证明
这里快指针要走两步，所以要判断fast和fast.next两个是否为空
快慢指针相遇的点到头节点的中点，就是环的起点。

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文