LeetCode 链表

\2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解答：

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = cur = ListNode(0)
        carry = 0
        
        while l1 or l2 or carry:
            temp = 0
            if l1:
                temp += l1.val
                l1 = l1.next
            if l2:
                temp += l2.val
                l2 = l2.next
            if carry:
                temp += carry
            carry = temp // 10
            cur.next = ListNode(temp % 10)
            cur = cur.next
        return dummy.next
                
改进：
def addTwoNumbers(self, l1, l2):
    dummy = cur = ListNode(0)
    carry = 0
    while l1 or l2 or carry:
        if l1:
            carry += l1.val
            l2 = l2.next
        if l2:
            carry += l2.val
            l2 = l2.next
        cur.next = ListNode(carry % 10)
        cur = cur.next
        carry //= 10
    return dummy.next

\19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

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

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        fast = slow = dummy = ListNode(0)
        dummy.next = head
        
        for _ in range(n):
            fast = fast.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        
        slow.next = slow.next.next
        
        return dummy.next

\21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

# iteratively
def mergeTwoLists1(self, l1, l2):
    dummy = cur = ListNode(0)
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 or l2
    return dummy.next
    
# recursively    
def mergeTwoLists2(self, l1, l2):
    if not l1 or not l2:
        return l1 or l2
    if l1.val < l2.val:
        l1.next = self.mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = self.mergeTwoLists(l1, l2.next)
        return l2
        
# in-place, iteratively        
def mergeTwoLists(self, l1, l2):
    if None in (l1, l2):
        return l1 or l2
    dummy = cur = ListNode(0)
    dummy.next = l1
    while l1 and l2:
        if l1.val < l2.val:
            l1 = l1.next
        else:
            nxt = cur.next
            cur.next = l2
            tmp = l2.next
            l2.next = nxt
            l2 = tmp
        cur = cur.next
    cur.next = l1 or l2
    return dummy.next

\23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

思路参考上题，采用二分法，两两组合。

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

class Solution:
    def merge2Lists(self, l1, l2):
            if not l1 or not l2:
                return l1 or l2
            if l1.val < l2.val:
                l1.next = self.merge2Lists(l1.next, l2)
                return l1
            else:
                l2.next = self.merge2Lists(l1, l2.next)
                return l2
            
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        if not lists:
            return None
        
        length = len(lists)
        while(length > 1):
            for i in range(length // 2):
                lists[i] = self.merge2Lists(lists[i], lists[length-1-i])
            length = (length + 1) // 2
            
        return lists[0]

方法二：pythonic的方法，使用heapq–堆队列算法

\24. Swap Nodes in Pairs**

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

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

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        cur = dummy 
        while cur.next and cur.next.next:
            first = cur.next
            second = cur.next.next
            first.next = second.next
            second.next = first
            cur.next = second
            cur = cur.next.next
       return dummy.next

\25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

• Only constant extra memory is allowed.

• You may not alter the values in the list’s nodes, only nodes itself may be changed.

  Reverse思路见下题，主要就是分成k组，分别使用reverse

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

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = jump = ListNode(0)
        dummy.next = left = right = head
        
        while True:
            count = 0
            while right and count < k:
                right = right.next
                count += 1
            if count == k:
                pre, cur = right, left
                for _ in range(k):
                    cur.next, pre, cur = pre, cur, cur.next
                jump.next, jump, l = pre, l, r
            else :
                return dummy.next

\206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

递归方法：

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        t = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return head

#迭代方法
#dummy head

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = dummy = ListNode(0)
        cur = dummy.next = head
        
        while cur and cur.next:
            tmp = pre.next
            pre.next = cur.next
            cur.next = cur.next.next
            pre.next.next = tmp
            
        return dummy.next
    
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = dummy = ListNode(0)
        cur = dummy.next = head
        
        while cur and cur.next:
            tmp = cur.next
            cur.next = tmp.next
            tmp.next = pre.next
            pre.next = tmp
        
        return dummy.next
    
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:     
        cur = None
        while head:
            nxt = head.next
            head.next = cur
            cur = head
            head = next
       return cur

\92. Reverse Linked List II

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

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

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        if not head or m == n:
            return head
        
        p = dummy = ListNode(0)
        dummy.next = head
        
        for _ in range(m-1):
            p = p.next
        tail = p.next
        
        for _ in range(m, n):
            tmp = p.next
            p.next = tail.next
            tail.next = tail.next.next
            p.next.next = tmp
        return dummy.next

\61. Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

思路一：连成环

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

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or k == 0:
            return head
        
        nxt = head
        length = 1
        while not nxt.next:
            length += 1
            nxt = nxt.next
        
        k = k % length
        nxt.next = head
        
        index = 0
        while index < (length - k):
            nxt = nxt.next
            index += 1
        
        r = nxt.next
        nxt.next = None
        return r

\83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

#Microsoft 一面

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

#Method 1
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        first = head
        while first:
            second = first.next
            while not second and first.val == second.val:
                second = second.next
            first.next = second
            first = second
        return head
#Method 2
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        p = head
        while p:
            while p.next and p.val == p.next.val:
                p.next = p.next.next
            p = p.next
        return head

\82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:

Input: 1->1->1->2->3
Output: 2->3

#Microsoft 一面

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

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

\86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

思路：本题大意，给定一个值x，在保持链表元素相对位置不变的情况下，小于x的元素在大于x的元素之前

​ 创建两个列表，遍历原始链表，第一个链表存储小的元素，第二个存储大的元素，最后拼接返回

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

class Solution:
    def partition(self, head, x):
        small = dummy_s = ListNode(0)
        big = dummy_b = ListNode(0)
        
        while head:
            if head.val < x:
                small.next = ListNode(head.val)
                small = small.next
            else:
                big.next = ListNode(head.val)
                big = big.next
            head = head.next
            
            small.next = dummy_b.next
            return dummy_s.next

\109. Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

思路：二叉树的递归定义为：左子树的值均小于根节点的值，右子树的值均大于根节点的值。（若左右子树不为空）。

​ 平衡树的递归定义为：左右子树的高度差小于等于1.

​ 因为给的数据是排序好的，又是一棵平衡树，所以用二分依次递归。与array的区别就是，不能用索引，只能用指针来将列表不断分割，方法：快慢指针，速度两倍。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return head
        if not head.next:
            return TreeNode(head.val)
        
        slow, fast = head, head.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        tmp = slow.next
        slow.next = None
        root = TreeNode(tmp.val)
        root.left = self.sortedListToBST(head)
		root.right = self.sortedListToBST(tmp.next)
        return root

\138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

1. You must return the copy of the given head as a reference to the cloned list.

题目大意：

​ 给你一个特殊的链表，你要复制它，这个链表的特殊部分在于多了random指针，random指针可以指向任意节点，若暴力方法，每当指向链表某一个节点你都要遍历找到那个结点，然后复制。时间肯定不满足要求，

方法一：使用HashMap将每个结点的值复制存储起来。然后第二轮对链表迭代，更新HashMap中的next和random指针。

"""
# Definition for a Node.
class Node:
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
"""
class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        dic = dict()
        m = n = head
        while m:
            dic[m] = Node(m.val, None, None)
            m = m.next
        while n:
            dic[n].next = dic.get(n.next)
            dic[n].random = dic.get(n.random)
            n = n.next
        return dic.get(head)

方法二：遍历指针是，在每一个结点后面复制一个结点，然后第二次迭代将两个链表分开

"""
# Definition for a Node.
class Node:
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        p = head
        while p != None:
            nxt = p.next
            
            copy = Node(p.val, None, None)
            p.next = copy
            copy.next = nxt
            
            p = nxt
            
        p = head
        while p :
            if not p.next.random:
                if p.random: #因为最终的None只有一个
                    p.next.random = p.random.next#注意复制结点的链接的是复制结点
                else:
                    p.next.random = None
            p = p.next.next
            
        p = head
        cur = dummy = ListNode(0)       
        while p and p.next:
            nxt = p.next.next
     
            cur.next = p.next
            cur = cur.next
            
            p.next = p.next.next
            p = p.next
            
        return dummy.next

\141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

思路：快慢指针，如果有环总会相遇

# 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:
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast is slow:
                return True
       return False

\142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up:
Can you solve it without using extra space?

思路如下：

# 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:
        slow, fast = head, head
        
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if slow is fast:
                slow = head
                while slow is not fast:
                    slow = slow.next
                    fast = fast.next
                return slow
       return None

\143. Reorder List

Given a singly linked list L: L0→L1→…→L**n-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→L**n-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

思路：快慢指针分为两个链表，第二个链表反转，然后两个链表合并。

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

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        fast, slow = head, head
        
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            
        pre, node = None, slow
        while slow:
            pre, node.next, node = node, pre, node.next
        first, second = head, pre
        
        while second and second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next
        return

\147. Insertion Sort List

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
3. It repeats until no input elements remain.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

思路：构造一个新链表，依次插入

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

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        
        pre = dummy = ListNode(0)
        cur = head
        nxt = None
        
        while cur:
            nxt = cur.next
            while pre.next and pre.next.val < cur.val:
                pre = pre.next
            
            cur.next = pre.next
            pre.next = cur
            pre = dummy
            cur = nxt
        return dummy.next

\148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

思路：nlogn -> merge sort

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

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        
        fast, slow = head.next, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
        second = slow.next
        slow.next = None
        
        l = self.sortList(head)
        r = self.sortList(second)
        return self.merge(l, r)
    
    def merge(self, l, r):
        if not l or not r:
            return l or r
        if l.val > r.val:
            l, r = r, l
        head = pre = l
        l = l.next
        
        while l and r:
            if l.val < r.val:
                pre.next = l
                l = l.next
            else:
                pre.next = r
                r = r.next
            pre = pre.next
            
        pre.next = l or r
        return head
    
    # def merge(self, l, r):
    #     if not l or not r:
    #         return l or r
    #     if l.val > r.val:
    #         l, r = r, l
    #     head = pre = l
    #     l = l.next
    #     while l and r:
    #         if l.val < r.val:
    #             l = l.next
    #         else:
    #             nxt = pre.next
    #             pre.next = r
    #             tmp = r.next
    #             r.next = nxt
    #             r = tmp
    #         pre = pre.next
    #     pre.next = l or r
    #     return head

\160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

#method 1: 需要距离
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        length_a = 0
        length_b = 0
        a, b = headA, headB
        while a:
            length_a += 1
            a = a.next
        while b:
            length_b += 1
            b = b.next
        a, b = headA, headB    
        if length_a < length_b:
            a, b = headB, headA
            length_a, length_b = length_b, length_a
        for _ in range(length_a-length_b):
            a = a.next
        
        while a or b:
            if a is b:
                return a
            else:
                a = a.next
                b = b.next
        return None
#method2:不需要距离
#因为链表中不存在环，所以当遍历完一个链表再遍历另一个，最终他们走过的距离一样，如果有公共结点则一定会相遇。
#否则两个同时到达 None
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        
        a, b = headA, headB      
        while a != b:
            a = headB if a is None else a.next
            b = headA if b is None else b.next
        return a

\203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val\.

Example:

Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

类似\82. Remove Duplicates from Sorted List II

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

\234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

水题，注意fast指针由于链表结点的奇偶情况，结束的不同情况。

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        fast, slow = head, head
        prev = None
        while fast and fast.next:
            fast = fast.next.next
            prev, prev.next, slow= slow, prev, slow.next#注意这里的赋值情况
        if fast:
            slow = slow.next
        while prev or slow:
            if prev.val != slow.val:
                return False
            prev = prev.next
            slow = slow.next
        return True

\237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list – head = [4,5,1,9], which looks like following:

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Note:

• The linked list will have at least two elements.
• All of the nodes’ values will be unique.
• The given node will not be the tail and it will always be a valid node of the linked list.
• Do not return anything from your function.

\237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list – head = [4,5,1,9], which looks like following:

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Note:

• The linked list will have at least two elements.

• All of the nodes’ values will be unique.

• The given node will not be the tail and it will always be a valid node of the linked list.

• Do not return anything from your function.

  奇葩题

  class Solution:
      def deleteNode(self, node):
          """
          :type node: ListNode
          :rtype: void Do not return anything, modify node in-place instead.
          """
          node.val = node.next.val
          node.next = node.next.next

\445. Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack_1 = []
        stack_2 = []
        cur1, cur2 = l1, l2
        carry = 0
        dummy = ListNode(0)
        while cur1:
            stack_1.append(cur1)
            cur1 = cur1.next
        while cur2:
            stack_2.append(cur2)
            cur2 = cur2.next
        while carry or stack_1 or stack_2:
            x1 = stack_1.pop().val if stack_1 else 0
            x2 = stack_2.pop().val if stack_2 else 0
            tmp = ListNode((x1 + x2 + carry) % 10)
            tmp.next = dummy.next
            dummy.next = tmp
            carry = (x1 + x2 + carry) // 10
        return dummy.next

\725. Split Linked List in Parts

Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”.

The length of each part should be as equal as possible: no two parts should have a size differing by more than 1. This may lead to some parts being null.

The parts should be in order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later.

Return a List of ListNode’s representing the linked list parts that are formed.

Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ]

Example 1:

Input:
root = [1, 2, 3], k = 5
Output: [[1],[2],[3],[],[]]
Explanation:
The input and each element of the output are ListNodes, not arrays.
For example, the input root has root.val = 1, root.next.val = 2, \root.next.next.val = 3, and root.next.next.next = null.
The first element output[0] has output[0].val = 1, output[0].next = null.
The last element output[4] is null, but it's string representation as a ListNode is [].

Example 2:

Input: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
Explanation:
The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.

Note:

The length of root will be in the range [0, 1000].

Each value of a node in the input will be an integer in the range [0, 999].

k will be an integer in the range [1, 50].

思路：参考大佬的题解

This question can be split into two parts

1. Count the length of the linked list
2. Determine the length of nodes in each chunk
3. Splitting the linked list up

At the end of step 2, res will look something like this, for a list of length 10 and k of 3: [4, 4, 3].

Step 3 iterates through res using the values in res and replaces the value at each index with each chunk’s head node. We have to keep a reference to prev in order to slice up the chunks nicely by setting prev.next = None.

- Yangshun

class Solution:
    def splitListToParts(self, root: ListNode, k: int) -> List[ListNode]:
        cur, length = root, 0
        while cur:
            cur, length = cur.next, length + 1
        
        chunk_size, longer_chunk = length // k, length % k
        res = [chunk_size + 1] * longer_chunk + [chunk_size] * (k - longer_chunk)
        
        prev, cur = None, root
        for i, num in enumerate(res):
            if prev:
                prev.next = None
            res[i] = cur
            for _ in range(num):
                prev, cur = cur, cur.next
        return res

\430. Flatten a Multilevel Doubly Linked List

You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.

Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation:

The multilevel linked list in the input is as follows:



After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation:

The input multilevel linked list is as follows:

  1---2---NULL
  |
  3---NULL

Example 3:

Input: head = []
Output: []

How multilevel linked list is represented in test case:

We use the multilevel linked list from Example 1 above:

1---2---3---4---5---6--NULL
        |
        7---8---9---10--NULL
            |
            11--12--NULL

The serialization of each level is as follows:

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

To serialize all levels together we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

Merging the serialization of each level and removing trailing nulls we obtain:

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

Constraints:

• Number of Nodes will not exceed 1000.

• 1 <= Node.val <= 10^5

  思路：使用栈

  """
  # Definition for a Node.
  class Node:
      def __init__(self, val, prev, next, child):
          self.val = val
          self.prev = prev
          self.next = next
          self.child = child
  """
  class Solution:
      def flatten(self, head: 'Node') -> 'Node':
          if not head:
              return head
          stk = [head]
          prev = Node(0)
          while stk:
              root = stk.pop()
              root.prev = prev
              prev.next = root
              prev = root
              if root.next:
                  stk.append(root.next)
              if root.child:
                  stk.append(root.child)
                  root.child = None
          head.prev = None
          return head

\817. Linked List Components

We are given head, the head node of a linked list containing unique integer values.

We are also given the list G, a subset of the values in the linked list.

Return the number of connected components in G, where two values are connected if they appear consecutively in the linked list.

Example 1:

Input: 
head: 0->1->2->3
G = [0, 1, 3]
Output: 2
Explanation: 
0 and 1 are connected, so [0, 1] and [3] are the two connected components.

Example 2:

Input: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
Output: 2
Explanation: 
0 and 1 are connected, 3 and 4 are connected, so [0, 1] and [3, 4] are the two connected components.

Note:

• If N is the length of the linked list given by head, 1 <= N <= 10000.

• The value of each node in the linked list will be in the range[0, N - 1].

• 1 <= G.length <= 10000.

• G is a subset of all values in the linked list.

  题目大意：给定一个链表，链表中的元素均不重复，给定一个列表G，是链表元素值的子集。返回G中的连续部分。

  算法：遍历每一个链表中的每一个元素，若这个元素在G中则遍历下一个，作为一个部分。直至遍历结束。

  class Solution:
      def numComponents(self, head: ListNode, G: List[int]) -> int:
          dic = {num: 1 for num in G}
          
          comp = []
          while head:
              cur = []
              while head and head.val in dic:
                  cur.append(head.val)
                  head = head.next
              if cur:
                  comp.append(cur)
              if head:
                  head = head.next
          return len(comp)
      
  class Solution:
      def numComponents(self, head: ListNode, G: List[int]) -> int:
          set_G = set(G)
          res = cnt = 0
          while head:
              if head.val in set_G:
                  cnt += 1
              else:
                  res += 1 if cnt else 0
              	cnt = 0
              head = head.next
         return res+1 if cnt else res

  \1019. Next Greater Node In Linked List

We are given a linked list with head as the first node. Let’s number the nodes in the list: node_1, node_2, node_3, ... etc.

Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.

Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).

Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.

Example 1:

Input: [2,1,5]
Output: [5,5,0]

Example 2:

Input: [2,7,4,3,5]
Output: [7,0,5,5,0]

Example 3:

Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]

Note:

1. 1 <= node.val <= 10^9 for each node in the linked list.
2. The given list has length in the range [0, 10000]

思路：本题要找每个元素的后续结点中第一个大于该节点的值，并输出。使用stack

class Solution:
    def nextLargerNodes(self, head: ListNode) -> List[int]:
        ans = []
        stack = []
        index = 0
        while head:
            ans.append(0)
            current_val = head.val
            while stack and stack[-1][0] < current_val:
                last_value = stack.pop()
                ans[last_value[1]] = current_val
             
            stack.append((current_val, index))
            head = head.next 
            index += 1
        return ans

\1171. Remove Zero Sum Consecutive Nodes from Linked List

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:

Input: head = [1,2,3,-3,-2]
Output: [1]

Constraints:

• The given linked list will contain between 1 and 1000 nodes.
• Each node in the linked list has -1000 <= node.val <= 1000.

思路：prefix，当prefix的值等于之前元素的prefix值时，说明这两个元素之间的元素之和为0。

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

class Solution:
    def removeZeroSumSublists(self, head):
        prefix = 0
        seen = {}
        seen[0] = dummy = ListNode(0)
        dummy.next = head
        
        while head:
            prefix += head.val
            seen[prefix] = head
            head = head.next
        head = dummy
        prefix = 0
        
        while head:
            prefix += head.val
            head.next = seen[prefix].next
            head = head.next
        return dummy.next