链表常见的使用方法逻辑整理

---

1. 链表特点

链表特点

• 由节点组成：链表是由一个个节点组成的数据结构，每个节点包含数据和指向下一个节点的引用（指针/链接）。
• 动态插入和删除：相对于数组，链表可以更轻松地进行节点的插入和删除操作，因为只需要调整节点的指针，而无需移动大量元素。
• 内存利用灵活：链表的节点在内存中不必连续存储，这使得链表可以更灵活地利用内存，但也可能导致对内存的随机访问效率较低。
• 随机访问效率低：链表的节点不能直接通过索引进行访问，需要从头节点开始逐个遍历，因此随机访问效率较低。
• 多种类型：链表有单向链表、双向链表和循环链表等不同类型，每种类型都有不同的特点和适用场景。

链表是一种由节点组成的线性数据结构，每个节点包含一个数据元素和一个指向下一个节点的指针。跟数据对比有差异

• 数组能够通过固定下标查找对应的数据，查找性能优越，但是每次插入/删除数据都需要将对应节点后续的数据整体挪移，因此数组的更新成本较大
• 链表更新节点时只需要重新插入一个新节点，并调整上下节点的指针，无需移动后续的所有节点，因此更新成本较小，但是当需要获取当个节点数据时，由于没有固定下标，因此必须从头开始查找，因此查询性能较差

两者类型的数据结构，分别在读写时表现有差异，因此需要根据不同的应用场景（读写的频率差异）进行合理使用

2. 链表创建

链表中的每一个元素都是一个节点，每个节点通常包含两部分：数据和下一个节点的引用。

class Node:
    def __init__(self, data):
        self.data = data  # 节点存储的数据
        self.next = None  # 默认下一个节点为空
        
class LinkedList:
    def __init__(self):
        self.head = None  # 初始链表为空

3. 链表遍历通用方法

3.1 在链表的开头添加元素

def add_first(self, data):
    new_node = Node(data)   # 创建新的节点
    new_node.next = self.head  # 将新节点指向当前的头节点
    self.head = new_node    # 更新头节点为新节点

LinkedList.add_first = add_first

3.2 在链表的结尾添加元素

def add_last(self, data):
    new_node = Node(data)
    if self.head is None:  # 若链表为空，则直接将新节点设置为头节点
        self.head = new_node
        return
    last_node = self.head  # 遍历到链表的尾部
    while last_node.next:
        last_node = last_node.next
    last_node.next = new_node  # 在链表尾部添加新节点

LinkedList.add_last = add_last

3.3 删除链表的第一个元素

def remove_first(self):
    if self.head:
        self.head = self.head.next  # 更新头节点为下一个节点

LinkedList.remove_first = remove_first

3.4 删除链表的最后一个元素

def remove_last(self):
    if self.head is None:  # 若链表为空，直接返回
        return
    if self.head.next is None:  # 若链表只有一个元素，将头节点设置为空
        self.head = None
        return
    second_to_last = self.head  # 找到倒数第二个节点
    while second_to_last.next.next:
        second_to_last = second_to_last.next
    second_to_last.next = None  # 将倒数第二个节点的next设置为空，从而删除最后一个节点

LinkedList.remove_last = remove_last

3.5 遍历链表

def print_list(self):
    current_node = self.head  # 从头节点开始遍历
    while current_node:
        print(current_node.data, end=" -> ")
        current_node = current_node.next  # 移动到下一个节点
    print("None")

LinkedList.print_list = print_list

3.6 查找链表中的元素

def search(self, target):
    current_node = self.head  # 从头节点开始遍历
    while current_node:
        if current_node.data == target:  # 若找到目标数据，返回True
            return True
        current_node = current_node.next  # 移动到下一个节点
    return False  # 遍历完链表后，未找到目标数据，返回False

LinkedList.search = search

3.7 反转链表

def reverse(self):
    prev = None  # 上一个节点
    current = self.head  # 当前节点
    while current:
        next_node = current.next  # 记录下一个节点
        current.next = prev  # 将当前节点指向上一个节点
        prev = current  # 更新上一个节点为当前节点
        current = next_node  # 移动到下一个节点
    self.head = prev  # 更新头节点

LinkedList.reverse = reverse

4. 常见面试题

一些总结

4.1 相交链表

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

图示两个链表在节点 c1 开始相交：

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

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

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA is None or headB is None:
            return

        pA, pB = headA, headB

        while pA != pB:
            pA = headB if pA is None else pA.next
            pB = headA if pB is None else pB.next

        return pA

4.2 反转链表

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

示例 1：

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

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

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

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre, cur = None, head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre 

4.3 环形链表

给你一个链表的头节点 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
解释：链表中没有环。

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

class Solution(object):
    def hasCycle(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """

        slow, fast = head, head
        while fast is not None and fast.next is not None and slow != None:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

4.4 环形链表 II

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

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

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

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

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow, fast = head, head
        while True:
            if not (fast and fast.next): return
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break

        first= head
        while first != slow:
            first, slow = first.next, slow.next
        
        return first

4.5 合并两个有序链表

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

示例 1：

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

示例 2：

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

示例 3：

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

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if not list1: return list2
        if not list2: return list1

        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        
        list2.next = self.mergeTwoLists(list1, list2.next)
        return list2        

4.6 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

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

示例 3：

输入：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(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        cur = dummy = ListNode()
        carry = 0
        while l1 or l2 or carry:
            # 做加合运算
            carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)
            # 如果超过10，需要做进位调整
            cur.next = ListNode(carry%10)
            #  取余数
            carry //= 10
            # 在一个节点
            cur = cur.next
            if l1: l1 = l1.next
            if l2: l2 = l2.next
        return dummy.next

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

给你一个链表，删除链表的倒数第 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]

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        slow = dummy_head = ListNode(next=head)
        fast = head
        while fast and n:
            fast = fast.next
            n -=1

        while fast:
            fast = fast.next
            slow = slow.next
        
        slow.next = slow.next.next
        return dummy_head.next
        

4.8 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

输入：head = []
输出：[]
示例 3：

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

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        p = ListNode(-1)
        a,b,p.next,tmp = p,p,head,p
        while b.next and b.next.next:
            a,b = a.next,b.next.next
            tmp.next,a.next,b.next = b,b.next,a
            tmp,b = a,a
        return p.next

5. 参考文档

暂无，相关面试题请参考leetcode以及相关说明