链表

链表初始化

• 单链表

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

• 双链表

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

2. 两数相加

2. 两数相加

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


class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        pass

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

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

# 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:
        dummy = ListNode(0)
        dummy.next = head
        # 删除倒数第 n 个，要先找倒数第 n + 1 个节点
        x = self.findFromEnd(dummy, n + 1)
        # 删掉倒数第 n 个节点
        x.next = x.next.next
        return dummy.next

    def findFromEnd(self, head: ListNode, k: int):
        p1 = head
        # p1 先走 n 步
        for i in range(k):
            p1 = p1.next
        p2 = head
        # p1 和 p2 同时走 n - k 步
        while p1:
            p2 = p2.next
            p1 = p1.next
        # p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
        return p2

21. 合并两个有序链表

21. 合并两个有序链表

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


class Solution:
    def mergeTwoLists(self, list1: ListNode, list2: ListNode):
        if list1 is None or list2 is None:
            return list2 if list1 is None else list1

        head = ListNode(0)

        if list1.val <= list2.val:
            head = list1
        else:
            head = list2

        cur1 = head.next
        if head == list1:
            cur2 = list2
        else:
            cur2 = list1
        pre = head
        while cur1 and cur2:
            if cur1.val <= cur2.val:
                pre.next = cur1
                cur1 = cur1.next
            else:
                pre.next = cur2
                cur2 = cur2.next
            pre = pre.next
        if cur1:
            pre.next = cur1
        else:
            pre.next = cur2
        return head

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

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

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


class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        new_head = head.next
        head.next = self.swapPairs(new_head.next)
        new_head.next = head
        return new_head

    def swapPairs2(self, head: ListNode) -> ListNode:
        res = ListNode(next=head)
        pre = res
        while pre.next and pre.next.next:
            cur = pre.next
            post = pre.next.next

            cur.next = post.next
            post.next = cur
            pre.next = post
            pre = pre.next.next

        return res.next

25. K 个一组翻转链表 💯

25. K 个一组翻转链表

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


class Solution:
    def reverseKGroup(self, head: ListNode, k: int):
        start = head
        end = self.get_group_end(start, k)
        if end is None:
            return head
        head = end

        self.reverse(start, end)
        last_end = start
        while last_end.next != None:
            start = last_end.next
            end = self.get_group_end(start, k)
            if end is None:
                return head
            self.reverse(start, end)
            last_end.next = end
            last_end = start
        return head

    def reverse(self, start: ListNode, end: ListNode):
        end = end.next
        pre = None
        cur = start
        next = None
        while cur != end:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        start.next = end

    def get_group_end(self, start: ListNode, k: int):
        while k != 0 and start:
            start = start.next
            k = k - 1
        return start

61. 旋转链表

61. 旋转链表

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

# 我们可以将链表先连成环，然后将链表在指定位置断开

# 先遍历一遍，求出链表节点个数 n。注意到 k 可能很大，我们只需将链表右移 k % n 个位置即可。

# 第二次遍历到 n - k % n 的位置，记录下断开后新链表头节点位置，再将其断开并返回新的头节点。


class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if k == 0 or not head or not head.next:
            return head
        n = 1
        cur = head
        # 遍历出链表的长度
        while cur.next:
            cur = cur.next
            n += 1

        cut = n - k % n
        cur.next = head
        while cut:
            cut -= 1
            cur = cur.next
        new_head = cur.next
        cur.next = None
        return new_head

82. 删除排序链表中的重复元素 II 💯

82. 删除排序链表中的重复元素 II

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


class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head

        # dummy = ListNode(0)
        # dummy.next = head
        dummy = ListNode(0, head)

        pre = dummy
        cur = head
        while cur:
            # 跳过当前的重复节点，使得cur指向当前重复元素的最后一个位置
            while cur.next and cur.val == cur.next.val:
                cur = cur.next
            if pre.next == cur:
                # pre和cur之间没有重复节点，pre后移
                pre = pre.next
            else:
                # pre->next指向cur的下一个位置（相当于跳过了当前的重复元素）
                # 但是pre不移动，仍然指向已经遍历的链表结尾
                pre.next = cur.next
            cur = cur.next
        return dummy.next

83. 删除排序链表中的重复元素

83. 删除排序链表中的重复元素

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


class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        cur = head
        while cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

86. 分隔链表

86. 分隔链表

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


class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        small = ListNode(0)
        large = ListNode(0)
        small_head = small
        large_head = large
        while head:
            if head.val < x:
                small.next = head
                small = small.next
            else:
                large.next = head
                large = large.next
            head = head.next
        large.next = None
        small.next = large_head.next
        return small_head.next

92. 反转链表 II

92. 反转链表 II

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

# 第 1 步：先将待反转的区域反转
# 第 2 步：把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ


class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        def reverse(head: ListNode):
            pre = None
            cur = head
            while cur:
                temp = cur.next
                cur.next = pre
                pre = cur
                cur = temp

        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        # 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
        for _ in range(left - 1):
            pre = pre.next
        # 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
        right_node = pre
        for _ in range(right - left + 1):
            right_node = right_node.next
        # 第 3 步：切断出一个子链表（截取链表）
        left_node = pre.next
        cur = right_node.next
        # 切断链接
        pre.next = None
        right_node.next = None
        # 第 4 步：同第 206 题，反转链表的子区间
        reverse(left_node)
        # 第 5 步：接回到原来的链表中
        pre.next = right_node
        left_node.next = cur
        return dummy.next

141. 环形链表

141. 环形链表

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


# 哈希表方式，遍历访问结点，并判断是否在哈希表中
# 快慢指针方式，两个指针相遇就说明有环

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # 快慢指针初始化指向 head
        slow = fast = head
        # 快指针走到末尾时停止
        while fast and fast.next:
            # 慢指针走一步，快指针走两步
            slow = slow.next
            fast = fast.next.next
            # 快慢指针相遇，说明含有环
            if slow == fast:
                return True
        return False

    def hasCycle2(self, head: ListNode) -> bool:
        visted = set()
        while head:
            if head in visted:
                return True
            visted.add(head)
            head = head.next
        return False

142. 环形链表 II

142. 环形链表 II

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


class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        # 快慢指针初始化指向 head
        slow = fast = head
        while fast and fast.next:
            # 慢指针走一步，快指针走两步
            slow = slow.next
            fast = fast.next.next
            # 快慢指针相遇，说明含有环
            if slow == fast:
                break
        # fast 遇到空指针说明没有环
        if fast is None or fast.next is None:
            return None
        slow = head
        # 快慢指针同步前进，相交点就是环起点
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow

147. 对链表进行插入排序

147. 对链表进行插入排序

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


class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head:
            return head

        dummy = ListNode(0)
        dummy.next = head
        last_sorted = head
        cur = head.next
        while cur:
            if last_sorted.val <= cur.val:
                last_sorted = last_sorted.next
            else:
                prev = dummy
                while prev.next.val <= cur.val:
                    prev = prev.next
                last_sorted.next = cur.next
                cur.next = prev.next
                prev.next = cur
            cur = last_sorted.next
        return dummy.next

148. 排序链表

148. 排序链表

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


class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        pass

160. 相交链表

160. 相交链表

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


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        pa = headA
        pb = headB
        while pa != pb:
            if not pa:
                pa = headB
            else:
                pa = pa.next
            if not pb:
                pb = headA
            else:
                pb = pb.next
        return pa

203. 移除链表元素

203. 移除链表元素

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


class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy_head = ListNode(0, next=head)
        cur = dummy_head
        while cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy_head.next

206. 反转链表 💯

206. 反转链表

# 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:
        pre = None
        cur = None
        while head:
            cur = head.next  # 抓手
            head.next = pre  # 反转
            pre = head
            head = cur      # 往下走
        return pre

234. 回文链表

234. 回文链表

# 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:
        stack = []
        cur = head
        while cur:
            stack.append(cur)
            cur = cur.next
        while stack:
            xxx = stack.pop()
            if xxx.val != head.val:
                return False
            head = head.next
        return True

328. 奇偶链表

328. 奇偶链表

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


class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head or not head.next or not head.next.next:
            return head

        even_head = head.next
        odd = head  # 奇
        even = even_head  # 偶

        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next

        odd.next = even_head
        return head

707. 设计链表 💯

707. 设计链表

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


class MyLinkedList:

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

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        cur = self.head
        for _ in range(index + 1):
            cur = cur.next
        return cur.val

    def addAtHead(self, val: int) -> None:
        new_node = ListNode(val)
        new_node.next = self.head.next
        self.head.next = new_node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        new_node = ListNode(val)
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0:
            self.addAtHead(val)
            return
        elif index == self.size:
            self.addAtTail(val)
            return
        elif index > self.size:
            return
        new_node = ListNode(val)
        pre = self.head
        while index:
            pre = pre.next
            index -= 1
        new_node.next = pre.next
        pre.next = new_node
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        pre = self.head
        while index:
            pre = pre.next
            index -= 1
        pre.next = pre.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)

876. 链表的中间结点

876. 链表的中间结点

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


class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        # 快慢指针初始化指向 head
        slow = fast = head
        # 快指针走到末尾时停止
        while fast and fast.next:
            # 慢指针走一步，快指针走两步
            slow = slow.next
            fast = fast.next.next
        # 慢指针指向中点
        return slow

面试题 02.07. 链表相交

链表相交

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


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        pa = headA
        pb = headB
        while pa != pb:
            if not pa:
                pa = headB
            else:
                pa = pa.next
            if not pb:
                pb = headA
            else:
                pb = pb.next
        return pa

剑指 Offer 22. 链表中倒数第 k 个节点

剑指 Offer 22. 链表中倒数第 k 个节点

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


class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        pass