链表

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

1、合并两个有序链表

https://leetcode-cn.com/problems/merge-two-sorted-lists/
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

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

1.1、递归法

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val < list2.val:
            # list1当前结点指向其他剩余的所有结点
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            # list2当前结点指向其他剩余的所有结点
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2

• 时间复杂度 O(n+m)，n和m分别为两个链表的长度
• 空间复杂度 O(n+m)，n和m分别为两个链表的长度，递归调用需要消耗栈的空间

该方法采用了递归的思想，如果list1当前结点小于list2当前结点，那么不需要排序，将list1当前结点的next指针指向除过list1的其他结点，否则，将list2当前结点的next指针指向除过list2的其他结点，直到有一个结点为空，此时两个链表已经排序完毕，为这种情况

再依次向前return返回指针，得到

2.1、迭代法

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # 一个哨兵结点
        prehead = ListNode(-1)
        # 设置一个指针
        prev = prehead
        while list1 and list2:
            if list1.val <= list2.val:
                # prev指向list1结点
                prev.next = list1
                # list1结点向下走一步
                list1 = list1.next
            else:
                prev.next = list2
                list2 = list2.next
             # prev指针向下走一步
            prev = prev.next
        prev.next = list1 if list1 is not None else list2
        return prehead.next

• 时间复杂度 O(n+m)，n和m分别为两个链表的长度
• 空间复杂度 O(1)，只维护了一个链表

该方法采用了迭代的思想，先设定一个哨兵结点 prehead ，再去维护一个prev指针，通过调整它的next指针，来构建排序完成后的链表。如果list1当前结点小于等于list2当前结点，那么prev指针指向list1当前结点，list1走向下一个结点，反之prev指针指向list2当前结点，list2走向下一个结点。每判断一次，prev指针向前走一步，知道有一个链表为空，这个时候，prev指针已经构建了一个排好序的列表，返回合并后的即可。prehead.next意思是去除哨兵结点后的链表。

2、判断链表是否有环

https://leetcode-cn.com/problems/linked-list-cycle/
给你一个链表的头节点 head ，判断链表中是否有环。

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

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

1、快慢指针

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 判断链表头结点以及头结点指针是否存在
        if not head or not head.next:
            return False
        # 初始化指针
        slow = head
        fast = head.next
        while slow != fast:
            # 快指针走的快，如果走完了，还没有，就没环
            if not fast or not fast.next:
                return False
            # 快指针 2步，慢指针 1步
            slow = slow.next
            fast = fast.next.next
        return True

• 时间复杂度 O(n)，n为链表长度
• 空间复杂度 O(1)，只使用了两个指针的额外空间

维护两个指针，慢指针一次走一步，快指针一次走两步，如果两个指针相遇，那么该指针存在环，因为我们while判断是快慢指针是否相等，所以，初始化时快指针需要比慢指针多一步，不然开始就相遇了。

3、输出链表倒数第k个节点

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

1、快慢指针

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        # 定义指针
        fast, slow = head, headclass Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 初始化fast指针到k的位置
        while fast and k > 0:
            fast, k = fast.next, k-1
        # 两个指针同时向前，每次一步
        while slow and fast:
            fast = fast.next
            slow = slow.next
        return slow

• 时间复杂度 O(n)
• 空间复杂度 O(1)

定义两个指针，即快慢指针。初始化，使慢指针位于head位置；快指针位于k所在位置，然后依次向前，每次前进一格，当fast指向null的时候，slow指针刚好在k所在的位置。这个时候，直接返回slow指针即可。

4、翻转链表

https://leetcode-cn.com/problems/reverse-linked-list/
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

1、双指针法

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, cur = None, head
        while cur:
            # 保存原本next指针
            tmp = cur.next
            # 将cur的next指针指向前继结点
            cur.next = prev
            # 前继结点向前走一步
            prev = cur
            # cur通过tmp保存的next向前走一步
            cur = tmp
        return cur

• 时间复杂度 O(n)，n为链表长度
• 空间复杂度 O(1)，只使用了两个常量空间

定义两个指针，一个为当前结点，一个为前继结点，用来构造新链表，每次循环，先存储当前结点的next指向，再将next指向为前继结点，这样就如下图所示。然后，prev向下走一步来访问下一结点，cur通过tmp来访问下一结点。

2、递归法

因为该算法中，递归导致要维护函数调用栈，空间复杂度为O(n)，增加了空间复杂度，但其思想可以参考。
https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/solution/jian-zhi-offer-24-fan-zhuan-lian-biao-die-dai-di-2/

5、删除链表中的结点

https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。

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

1、双指针法

class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        # 如果head的值就是val，返回head的next，即跳过目标val的链表
        if head.val = val:
            return head.next
        # 定义两个指针
        prev, cur = head, head.next
        # 当cur的val等于目标val并且cur存在时
        while cur and cur.val != val:
            prev, cur = cur, cur.next
        if cur:
            prev.next = cur.next
        return head

首先，边界值判断，如果head的val等于目标val，就返回head的next指针指向。定义两个指针，前继指针和游标指针。prev和cur指针每次走一步，直到cur的val等于目标val并且cur存在时，这个时候，cur就是要删除的结点。如果cur存在，那么将prev的next指向cur的next指向，即prev的下下一个结点。返回head即可。

6、两个链表的第一个公共节点

https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：

在节点 c1 开始相交。

1、双指针法

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        node1, node2 = headA, headB
        while node1 != node2:
            node1 = node1.next if node1 else headB
            node2 = node2.next if node2 else headA
        return node1

• 时间复杂度 O(m+n)
• 空间复杂度 O(1)

该方法通过定义两个指针，初始化为headA和headB，每次向前走一步，当指针走向结点末尾时，将该指针指向对面链表的头部，这样当他们相遇时，所指向额结点就是第一个公共结点。