Leecode 链表

链表的概念

• 链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

单链表、双链表、循环链表

• 单向链表只有一个指针域，在整个节点中数据域用来存储数据元素，指针域用于指向下一个具有相同结构的节点。
• 双链表的每一个节点给中既有指向下一个结点的指针，也有指向上一个结点的指针，可以快速的找到当前节点的前一个节点，适用于需要双向查找节点值的情况。
  

链表和数组的区别

存储

• 数组静态分配内存，链表动态分配内存。 数组在内存中是连续的，链表是不连续的。
• 数组利用下标定位，查找的时间复杂度是O(1)，链表通过遍历定位元素，查找的时间复杂度是O(N)。
• 数组插入和删除需要移动其他元素，时间复杂度是O(N)，链表的插入或删除不需要移动其他元素，时间复杂度是O(1)。

数组优缺点
数组的优点

• 随机访问性比较强，可以通过下标进行快速定位。
• 查找速度快

数组的缺点

• 插入和删除的效率低，需要移动其他元素。
• 会造成内存的浪费，因为内存是连续的，所以在申请数组的时候就必须规定七内存的大小，如果不合 适，就会造成内存的浪费。
• 内存空间要求高，创建一个数组，必须要有足够的连续内存空间。
• 数组的大小是固定的，在创建数组的时候就已经规定好，不能动态拓展。

链表的优点

• 插入和删除的效率高，只需要改变指针的指向就可以进行插入和删除。
• 内存利用率高，不会浪费内存，可以使用内存中细小的不连续的空间，只有在需要的时候才去创建空间。
• 大小不固定，拓展很灵活。

链表的缺点

• 查找的效率低，因为链表是从第一个节点向后遍历查找。

双链表相对于单链表的优点：
  删除单链表中的某个节点时，一定要得到待删除节点的前驱，得到其前驱的方法一般是在定位待删除节点的时候一路保存当前节点的前驱，这样指针的总的的移动操作为2n次，如果是用双链表，就不需要去定位前驱，所以指针的总的的移动操作为n次。
  查找时也是一样的，可以用二分法的思路，从头节点向后和尾节点向前同时进行，这样效率也可以提高一倍，但是为什么市场上对于单链表的使用要超过双链表呢？从存储结构来看，每一个双链表的节点都比单链表的节点多一个指针，如果长度是n，就需要n*lenght（32位是4字节，64位是8字节）的空间，这在一些追求时间效率不高的应用下就不适用了，因为他占的空间大于单链表的1/3，所以设计者就会一时间换空间。

链表环问题

判断是否有环
  定义一个快指针和一个慢指针，快指针一次走两步，慢指针一次走两步，会出现两种情况，情况一指针走到了空的位置，那就说明这个链表不带环。情况二两个指针相遇，说明这个链表带环。

获得入环节点
  如果不考虑空间复杂度，可以使用一个map来记录走过的节点，这个指针一直向后遍历如果遇到空，说明这个链表不带环，也就没有入环节点，如果没有遇到空，如果遇到第一个在map中存在的节点，就说明回到了出发点，这个节点就是环的入口节点。如果不建立额外的空间，先使用快慢指针判断这个链表是否有环，如果有环将相遇节点记录，然后一个指针从链表的起始位置开始一次走一步，另一个指针从记录的节点开始一次走一步，当两个节点再次相遇，这个相遇节点就是环的入口节点。

https://leetcode.cn/problems/middle-of-the-linked-list/solution/kuai-man-zhi-zhen-zhu-yao-zai-yu-diao-shi-by-liwei/

环形链表

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if fast == slow:
                return True

        return False
1
2
3
4
5
6
7
8
9
10

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
1
2
3

解答

# https://leetcode.cn/problems/reverse-linked-list/solution/shi-pin-tu-jie-206-fan-zhuan-lian-biao-d-zvli/
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre, cur = None, head
        while cur:
            nxt = cur.next
            cur.next = pre
            pre = cur
            cur = nxt
            

        return pre
1
2
3
4
5
6
7
8
9
10
11
12

反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
1
2
3
4
5

解答

# 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: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        """
        思路：
            1、找到left之前的节点，即反转前的节点；
            2、反转节点，同时记录反转节点前的前驱节点，反转后的结果拼接在前驱节点上；
            3、拼接尾段不需要拼接的节点。
        """
        prehead = ListNode(-1)
        prehead.next = head
        pre = prehead
        # 遍历翻转前节点
        for i in range(left - 1):
            pre = pre.next

        # 获取前驱节点
        tail = pre
        # 翻转节点
        prev1, cur = None, pre.next
        for i in range(right - left + 1):
            nxt = cur.next
            cur.next = prev1
            prev1 = cur
            cur = nxt
       # tail: ListNode{val: 1, next: ListNode{val: 2, next: None}} 
	   # cur: ListNode{val: 5, next: None}
	   # prev1: ListNode{val: 4, next: ListNode{val: 3, next: ListNode{val: 2, next: None}}}
		
       # 拼接翻转节点
        tail.next.next = cur
        # 拼接尾节点
        tail.next = prev1

        return prehead.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
27
28
29
30
31
32
33
34
35
36
37
38
39

链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。

示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])

示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
1
2
3
4
5
6
7
8
9
10

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        # method one
        """
        A = [head]
        while A[-1].next:
            A.append(A[-1].next)
        return A[len(A) // 2]
        """

        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

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

160. 相交链表

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

# 若相交，链表A： a+c, 链表B : b+c. a+c+b+c = b+c+a+c 。则会在公共处c起点相遇。若不相交，a + b = b + a 。因此相遇处是NULL
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        if not all([headA, headB]):
            return None

        p1, p2 = headA, headB
        while p1 != p2:
            p1 = headB if p1 is None else p1.next
            p2 = headA if p2 is None else p2.next

        return p1
1
2
3
4
5
6
7
8
9
10
11
12

参考

链表（图文详解）