Guff_9hys

这个屌丝很懒，什么也没留下！

热门标签

[LeetCode]-Python刷题第二周（链表）_python中you are given the heads of two sorted linke

作者：Guff_9hys | 2024-08-20 04:10:49

踩

python中you are given the heads of two sorted linked lists list1 and list2.

4.Median of Two Sorted Arrays 求两个有序数组的中位数（Hard）

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:
nums1 = [1, 3]
nums2 = [2]
 
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
 
The median is (2 + 3)/2 = 2.5

二分搜索Binary Search，T：O(log(m+n))。

首先要知道：两个有序数组A(m), B(n)，k = (m+n)/2，奇数时找k+1大的数，偶数是找第k大和第k+1大的数再除2。

关键是找第k大的数，也就是两个数组合并之后的中间值，此时K=(m+n)/2。先在A，B中分别找第k/2大的数，如果A[k/2-1]==B[k/2-1],也就是A和B中第k/2个值相等，那么这个数就是两个数组中第k大的数。如果A[k/2-1]<B[k/2-1], 那么说明A[0]到A[k/2-1]都不可能是第k大的数，所以需要舍弃已经算出来的这个k/2，继续从A[k/2]到A[A.length-1]继续找。

当然，因为这里舍弃了A[0]到A[k/2-1]这k/2个数，那么第k大也就变成了第k-k/2个大的数了。如果 A[k/2-1]>B[k/2-1]，那么说明B[0]到B[k/2-1]都不可能是第k大的数，舍弃这k/2。如此迭代或者递归操作，如果有一个数组为空了，则返回另一个数组的第k大(剩下需要二分长度)的数。如果k==1，只需返回此时所以数中排第一小的数，就返回此时A，B中第一个元素小的那个。


class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        len1, len2 = len(nums1), len(nums2)
        if (len1 + len2) % 2 == 1:    #两个数组的和是奇数
            return self.getKth(nums1, nums2, (len1 + len2)/2 + 1)
        else:                         #两个数组的和是偶数
            return (self.getKth(nums1, nums2, (len1 + len2)/2) + \
                    self.getKth(nums1, nums2, (len1 + len2)/2 + 1)) * 0.5
 
    def getKth(self, A, B, k):        #找出第K个值
        m, n = len(A), len(B)
        if m > n:
            return self.getKth(B, A, k)
 
        left, right = 0, m   
        while left < right:
            mid = left + (right - left) / 2
            if 0 <= k - 1 - mid < n and A[mid] >= B[k - 1 - mid]:
                right = mid
            else:
                left = mid + 1
 
        Ai_minus_1 = A[left - 1] if left - 1 >= 0 else float("-inf")
        Bj = B[k - 1 - left] if k - 1 - left >= 0 else float("-inf")
 
        return max(Ai_minus_1, Bj)

376.Wiggle Subsequence 摆动子序列（Medium）

A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Example 1:
Input: [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence.
Example 2:
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Example 3:
Input: [1,2,3,4,5,6,7,8,9]
Output: 2
Follow up:
Can you do it in O(n) time?

本题要求在O(n)时间内求解。用delta储存相邻两个数的差，如果相邻的两个delta不同负号，那么说明子序列摇摆了一次。参看下图的nums的plot。这个例子的答案是7。平的线段部分我们支取最左边的一个点。除了最左边的边界点，我们要求delta != 0, 并且newDelta * delta <= 0。（这里不能只取<号），否则dot 5和7就会被忽略，因为他们的newDelta*delta = 0。


class Solution(object):
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n <= 1:
            return n
        
        delta = nums[1] - nums[0]
        cnt = 1 + (delta != 0)
        
        for i in range(1, n-1):
            newDelta = nums[i+1] - nums[i]
            if newDelta != 0 and newDelta*delta <= 0:
                cnt += 1
                delta = newDelta
        return cnt

376.Find the Celebrity 寻找名人（medium）

Suppose you are at a party with n people (labeled from 0 to n - 1) and among them, there may exist one celebrity. The definition of a celebrity is that all the other n - 1people know him/her but he/she does not know any of them.

Now you want to find out who the celebrity is or verify that there is not one. The only thing you are allowed to do is to ask questions like: "Hi, A. Do you know B?" to get information of whether A knows B. You need to find out the celebrity (or verify there is not one) by asking as few questions as possible (in the asymptotic sense).

You are given a helper function bool knows(a, b) which tells you whether A knows B. Implement a function int findCelebrity(n), your function should minimize the number of calls to knows.

Note: There will be exactly one celebrity if he/she is in the party. Return the celebrity's label if there is a celebrity in the party. If there is no celebrity, return -1.

在一个派对上有n个人，其中有一位名人。名人的定义是其他n-1个人都认识他，但他不认识任何一个人。要找出这位名人，只允许问A是否认识B。实施一个函数，找出名人，如果有返回他的label，如果没有返回-1。

先设定候选人res为0，从1开始遍历数组，对于遍历到的人i，若候选人res认识i，则将候选人res设为i。第一次遍历完毕以后，再开始第二次遍历，来判断res是否确实为解。T: O(n), S: O(1)


class Solution(object):
    def findCelebrity(self, n):
        """
        :type n: int
        :rtype: int
        """
        candidate = 0
        # Find the candidate.
        for i in xrange(1, n):
            if knows(candidate, i):  # All candidates < i are not celebrity candidates.
                candidate = i
        # Verify the candidate.
        for i in xrange(n):
            if i != candidate and (knows(candidate, i) \
                or not knows(i, candidate)):
                return -1
        return candidate

19.Remove Nth Node From End of List 移除链表倒数第N个节点（medium）

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?

解法1: two pass，先求出链表的总长度，然后在删除node

解法2：双指针，经典题。主要是在一个遍历中找到第n个倒数元素，一个指针先走n步，然后两个指针同步走，直到第一个走到终点，第二个指针指向的就是需要删除的节点。Corner case: head == null; 头节点的处理，比如，1->2->NULL, n =2; 这时，要删除的就是头节点。


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        slow, fast = dummy, dummy
         
        for i in xrange(n):
            fast = fast.next
             
        while fast.next:
            slow, fast = slow.next, fast.next
             
        slow.next = slow.next.next
         
        return dummy.next

83. Remove Duplicates from Sorted List移除有序链表中的重复项（Easy）

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

移除有序链表中的重复项，返回新链表。定义1个指针指向链表的第一个元素，然后第一个元素和第二个元素比较，如果重复，则删掉第二个元素，如果不重复，指针指向第二个元素。


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
         
        dummy = ListNode(0)
        dummy.next = head
 
        while head and head.next:           
            if head.val == head.next.val:
                head.next = head.next.next
            else:            
                head = head.next  
             
        return dummy.next

203.Remove Linked List Elements 移除链表元素（Easy）

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


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        while head and head.val == val:
            head = head.next
 
        if head:
            head.next = self.removeElements(head.next, val)
 
        return head


class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: ListNode
        :type val: int
        :rtype: ListNode
        """
        if not head:
            return None
         
        head.next = self.removeElements(head.next, val)
         
        return head.next if head.val == val else head


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    # @param {ListNode} head
    # @param {integer} val
    # @return {ListNode}
    def removeElements(self, head, val):
        dummy = ListNode(float("-inf"))
        dummy.next = head
        prev, curr = dummy, dummy.next
         
        while curr:
            if curr.val == val:
                prev.next = curr.next
            else:
                prev = curr
             
            curr = curr.next
         
        return dummy.next


def removeElements(self, head, val):      
        dummy = ListNode(-1)
        dummy.next = head
        pointer = dummy
         
        while(pointer.next):
             
            if pointer.next.val == val:
                pointer.next = pointer.next.next
            else:
                pointer = pointer.next
                 
        return dummy.next

237.Delte Node in a Linked List 删除链表的节点（Easy）

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.

解法：先把next节点的值赋给当前节点，在把当前节点的next变成当前节点的next.next。


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    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

61. Rotate List 旋转链表（Medium）

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

要注意当k大于链表长度时的处理，需要先遍历一遍得到链表长度n，然后k对n取余，用余数来翻转。


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if not head or not head.next:
            return head
 
        n, cur = 1, head
        while cur.next:
            cur = cur.next
            n += 1
        cur.next = head
 
        cur, tail = head, cur
        for _ in xrange(n - k % n):
            tail = cur
            cur = cur.next
        tail.next = None
 
        return cur

92.Reverse Linked List II 反向链表 II （Medium）

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

先建立一个新list node: dummy，用dummy链接m之前不用反向的node，然后反向m~n的节点，最后在把反向的连接起来。


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        dummyNode = ListNode(0)
        p = dummyNode
        q = head
 
        for x in range(m - 1):
            p.next = q
            q = q.next
            p = p.next
 
        start = None
        end = q
        next = None
        for x in range(m, n + 1):
            next = q.next
            q.next = start
            start = q
            q = next
 
        p.next = start
        end.next = next
        return dummyNode.next

206.Reverse Linked List 反向链表（Easy）

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?

反向链表，分别用递归和迭代方式实现。

递归Iteration：

新建一个node(value=任意值, next = None)，用一个变量 next 记录head.next，head.next指向新node.next，新 node.next 指向head，next 进入下一个循环，重复操作，直到结束。

迭代Recursion：

假设有链表1 -> 2 -> 3 -> 4 -> 5要进行反转，第一层先把1 -> 2 -> 3 -> 4 -> 5和None传入递归函数(head, newhead)，先记录head的next(2 -> 3 -> 4 -> 5)，head(1)指向newhead(None)变成(1->None)，然后把(2 -> 3 -> 4 -> 5, 1 -> None)递归传入下一层，记录head的next(3 -> 4 -> 5)，head(2)指向newhead(1->None)变成(2 -> 1->None)，然后把(3 -> 4 -> 5, 2 -> 1 -> None)递归传入下一层，直到最后head=None时返回newhead，此时 newhead = 5 -> 4 -> 3 -> 2 -> 1 -> None


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev = None
        while head:
            curr = head
            head = head.next
            curr.next = prev
            prev = curr
        return prev
 
 
 
 
 
def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur, prev = head, None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        return prev
 
 
 
 
 
Python: Recrusion
class Solution(object):
    def reverseList(self, head, prev=None):
        if not head:
          return prev
   
        curr, head.next = head.next, prev
        return self.reverseList(curr, head)
 
 
　　
Python: Recursion
class Solution:
    def reverseList(self, head):
        return self.doReverse(head, None)
    def doReverse(self, head, newHead):
        if head is None:
            return newHead
        next = head.next
        head.next = newHead
        return self.doReverse(next, head)

2.Add Two Numbers 两个数字相加（Medium）

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.

给定两个链表分别代表两个非负整数。数位以倒序存储，并且每一个节点包含一位数字。将两个数字相加并以链表形式返回。题目不难，主要考察链表操作和加法进位。

进位 = sum / 10，当前位值 = sum % 10


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        head = ListNode(0)
        l = head
        carry = 0
        while l1 or l2 or carry:
            sum, carry = carry, 0
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next
            if sum > 9:
                carry = 1
                sum -= 10
            l.next = ListNode(sum)
            l = l.next
        return head.next

21.Merge Two Sorted Lists 合并有序链表（Easy）

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

解法1：dummy list，新建一个链表，然后两个链表中从头各取一个元素进行比较，小的写入新链表，直到结束，返回dummy.next。

解法2：recursion，代码简洁，但空间复杂度高O(n)


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        curr = dummy = ListNode(0)
        while l1 and l2:
            if l1.val < l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        curr.next = l1 or l2
        return dummy.next

445. Add Two Numbers II 两个数字相加 II（Medium）

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

2. Add Two Numbers 的变形，之前的题最高位在链表末位，此题链表头部表示高位，尾部表示低位，不允许反转链表。两个数相加需要从低位开始。可以利用Stack的特点后进先出，遍历两个链表，将数字分别压入两个栈s1和s2，然后开始循环，如果栈不为空，则将栈顶数字加入sum中。


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        stk1, stk2 = [], []
        while l1:       #将L1的值都压入一个栈
            stk1.append(l1.val)
            l1 = l1.next
        while l2:       #将L2的值都压入一个栈
            stk2.append(l2.val)
            l2 = l2.next
 
        prev, head = None, None
        sum = 0
        while stk1 or stk2:       #两个其中任何一个为真
            sum /= 10
            if stk1:   #如果栈1不为空，就把栈里边最上边的数取出来加到sum上。
                sum += stk1.pop()
            if stk2:   ##如果栈2不为空，就把栈里边最上边的数取出来加到sum上。
                sum += stk2.pop()
             
            head = ListNode(sum % 10)   #把余数得到的值放在头结点上，
            head.next = prev       #头结点的下一个指针指向None
            prev = head            #prev指向头结点，返回去继续循环
 
        if sum >= 10:        #后边的功能是若最后的sum是10，则将进一位
            head = ListNode(sum / 10)
            head.next = prev*/
 
        return head

141. Linked List Cycle 链表中的环（Easy）

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?

给定一个链表，判断是否有环存在。Follow up: 不使用额外空间。

解法：双指针，一个慢指针每次走1步，一个快指针每次走2步的，如果有环的话，两个指针肯定会相遇。


# 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
        """
        fast, slow = head, head           #定义了双指针，一个快，一个慢
        while fast and fast.next:         #当快指针和快指针指向的下一个节点为真
            fast, slow = fast.next.next, slow.next         #那么快指针走两步，慢指针走一步
            if fast is slow:              #如果快指针和慢指针相等
                return True       #那么说明有一个环，否则就没有
        return False

142. Linked List Cycle II 链表中的环 II（medium）

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?

141. Linked List Cycle 的拓展，这题要返回环开始的节点，如果没有环返回null。

解法：双指针，还是用快慢两个指针，相遇时记下节点。


# 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
        """
        fast, slow = head, head     #定义两个快慢指针
        while fast and fast.next:      #当快指针和慢指针指向的下一个节点都为真的时候，开始循环
            fast, slow = fast.next.next, slow.next     #快指针走的快，慢指针走得慢，直到相遇
            if fast is slow:        #当两个指针相遇之后，
                fast = head         #将头节点地址赋值快指针，这时候，fast指向头结点
                while fast is not slow:      #如果这时候，fast和slow指针不是一个节点的话，快指针和慢指针都开始往下走
                                             #但是，快指针是从头结点开始走的，慢指针是从相遇节点开始走的。当他们相遇的                                              #时候，返回快指针指向的节点。
                    fast, slow = fast.next, slow.next     #两个指针以同样的速度往下走，下一次相遇的节点就是循环开始的                                                            #点
                return fast
        return None

725.Split Linked List in Parts 拆分链表成部分（Medium）

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].

题目描述：给定一个单链表，写一个函数把它分成k个单链表。分割成的k个单链表中，两两之间长度差不超过1，允许为空。分成的k个链表中，顺序要和原先的保持一致，比如说每个单链表有3个结点，则第一个单链表的结点为输入链表的前三个结点，依次类推。
思路：

第一次遍历单链表，求出链表的长度length；
求出平均分成的k个链表中，每个的结点avg，以及还多余的结点rem；
第二次遍历输入链表，如果达到avg，且rem存在值，则把本次遍历的结果赋值给结果数组；


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def splitListToParts(self, root, k):
        """
        :type root: ListNode
        :type k: int
        :rtype: List[ListNode]
        """
        ret = [None] * k  # 结果
        length, move = 0, root
        
        #求这个root的长度
        while move:   
            length += 1
            move = move.next
            
        avg, rem = length / k, length % k
        move, indexs = root, 0  # 结果数组索引
        while move:
            tmp = move
            pre = ListNode(0)  # 当前结点的前一个结点
            pre.next = move    #前一个节点的next指的是当前节点
            num = 0
            while num < avg:  # 平均分给每个k的结点数目，当分出来的部分多一圈的时候：
                pre, move = pre.next, move.next
                num += 1
            if rem:  # 平分之后还应该分给前rem个链表每个一个结点
                pre, move = pre.next, move.next
                rem -= 1
            pre.next = None
            ret[indexs] = tmp
            indexs += 1
        return ret

86. Partition List 划分链表（medium）

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值的前面，两部分的节点顺序不变。

解法：维护两个queue，一个存小于x值的，一个存大于等于x值的，最后在把两个连在一起。记得把大于等于的最后加上null。


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def partition(self, head, x):
        """
        :type head: ListNode
        :type x: int
        :rtype: ListNode
        """
        dummySmaller, dummyGreater = ListNode(-1), ListNode(-1)    #建立两个链表，一个存小于X的值，一个存，大于X的值
        smaller, greater = dummySmaller, dummyGreater
 
        while head:    #当链表存在时:
            if head.val < x:    #如果头结点的值小于x的值：
                smaller.next = head     #将头节点的地址赋给小链表的下一个指针指示的值
                smaller = smaller.next      
            else:           #如果头结点的值大于x的值：
                greater.next = head
                greater = greater.next
            head = head.next       #循环下一个节点
 
        smaller.next = dummyGreater.next   #然后把两个链表结合在一起
        greater.next = None    #给最后的大链表加上Null结尾
 
        return dummySmaller.next   #返回小链表的首地址

707. Design Linked List 设计链表（Easy）

Design your implementation of the linked list. You can choose to use the singly linked list or the doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement these functions in your linked list class:

get(index) : Get the value of the index-th node in the linked list. If the index is invalid, return -1.
addAtHead(val) : Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
addAtTail(val) : Append a node of value val to the last element of the linked list.
addAtIndex(index, val) : Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
deleteAtIndex(index) : Delete the index-th node in the linked list, if the index is valid.

Example:
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2);  // linked list becomes 1->2->3
linkedList.get(1);            // returns 2
linkedList.deleteAtIndex(1);  // now the linked list is 1->3
linkedList.get(1);            // returns 3
Note:

All values will be in the range of [1, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in LinkedList library.

自己设计一个链表可以实现各种功能。


#定义一个链表
class Node(object):  
    def __init__(self, val):
        self.val = val
        self.next = None
 
class MyLinkedList(object):
 
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.head = None
        self.size = 0
    
    #从链表中取得一个数
    def get(self, index):
        """
        Get the value of the index-th node in the linked list. If the index is invalid, return -1.
        :type index: int
        :rtype: int
        """
        if index < 0 or index >= self.size:   #如果超出链表范围则返回-1
            return -1
        elif self.head is None:    #如果链表为空返回-1
            return -1
        else:
            curr = self.head      #否则把链表头结点赋值给curr
        #从头便遍历到要取得标签这里，然后取数
        for i in range(index):
            curr = curr.next
        return curr.val
 
    #在链表头部加一个数，这个新数作为链表的头结点
    def addAtHead(self, val):
        """
        Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
        :type val: int
        :rtype: None
        """
        node = Node(val)    #把这个数放在类中，表明他此时具有类的两个属性
        node.next = self.head     #然后把原来的头结点放在新节点的后边
        self.head = node     #然后把新节点作为头结点
 
        self.size += 1      #链表的尺寸增加1
        
        
    #在链表的尾部增加一个节点
    def addAtTail(self, val):
        """
        Append a node of value val to the last element of the linked list.
        :type val: int
        :rtype: None
        """
        node = Node(val)     #同样把这个值，引入类中，获得类的属性
        curr = self.head     #把头结点赋值给curr指针
        if curr is None:     #如果当前节点是空，那么这个新节点就是头结点
            self.head = Node(val)
        else:           #如果当前节点不为空，则从头遍历这个链表直到最后
            for i in range(self.size-1):
                curr = curr.next   #此时的curr指的是最后一个有真值的节点
                if curr.next is None:    #如果遇到next指针指的是None的时候，就跳出循环
                    break
            curr.next = node    #然后把新的节点赋值给最后一个有值的节点的next处
        self.size += 1    #同样，节点数加1
        
 
    #在指定位置加一个节点
    def addAtIndex(self, index, val):
        """
        Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
        :type index: int
        :type val: int
        :rtype: None
        """
        if index < 0 or index > self.size:    #如果索引值超出链表长度，则返回-1
            return -1
 
        if index == 0:     #如果要插入的位置是第一个，就调用之前的函数
            self.addAtHead(val)
        else:         #如果不是第一个：
            curr = self.head     #同样把头节点赋值给当前指针
            for i in range(index - 1):     #然后从头到索引值依次遍历
                curr = curr.next   #使得curr指针指的是要插入的位置
            node = Node(val)   #把这个值引入类中，成为一个节点
            node.next = curr.next  #把链表后边的节点连接到新节点的后边
            curr.next = node      #新的节点作为插入位置的下一个值插入
 
            self.size += 1    #链表尺寸长度加1
            
            
    #删除链表指定位置的节点
    def deleteAtIndex(self, index):
        """
        Delete the index-th node in the linked list, if the index is valid.
        :type index: int
        :rtype: None
        """
        if index < 0 or index >= self.size:   #同样，如果索引值超过链表范围就返回-1
            return -1
 
        curr = self.head  #curr指向头节点
        if index == 0:    #如果要删除的索引值是第一个值
            self.head = curr.next    #就把第二个节点作为头节点
        else:    #如果不是第一个索引
            for i in range(index - 1):#遍历索引值前边的所有节点
                curr = curr.next     #此时curr指的是索引值的前一个节点
            curr.next = curr.next.next     #把要删除的节点后边的链表放在前边链表的next下
 
        self.size -= 1   #链表的长度减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)

817. Linked List Components 链接列表组件 (Medium)

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中，而下一个节点是空或者节点值不在G中，那么就是一个新的分段呗。


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def numComponents(self, head, G):
        """
        :type head: ListNode
        :type G: List[int]
        :rtype: int
        """
        groups = 0
        subset = set(G)   #set() 函数创建一个无序不重复元素集，可进行关系测试，删除重复数据，还可以计算交集、差集、并集等。
        while head:    #当链表指针为真时，循环。。。。
            if head.val in subset and (not head.next or head.next.val not in subset):#如果指针这个值在子集中并且（指针的下一个值为假或者指针的下一个值不在子集中），就加1
                groups += 1
            head = head.next   #然后头指针向后移一个节点
        return groups   #返回这个值

876. Middle of the Linked List 找出链表的中间节点（Easy）

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

If there are two middle nodes, return the second middle node.

Example 1:
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.
Example 2:
Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.
Note:

The number of nodes in the given list will be between 1 and 100.


# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution(object):
    def middleNode(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow=fast=head    #将链表的头节点，赋值给两个指针
        while fast and fast.next:   #当fast指针和fast.next指针指向为真的时候，循环;
            slow=slow.next    #将slow指针向后走一步
            fast=fast.next.next    #fast指针向后走两步，这个时候，当fast指针走到终点的时候，slow指针正好走到中间节点。
        return slow

声明：本文采用的程序或者解法大部分借鉴了其他作者的思路，就不一一声明了，如果侵权，请联系删除。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Guff_9hys/article/detail/1005114?site

[LeetCode]-Python刷题第二周（链表）_python中you are given the heads of two sorted linke

4.Median of Two Sorted Arrays 求两个有序数组的中位数（Hard）

二分搜索Binary Search，T：O(log(m+n))。

首先要知道：两个有序数组A(m), B(n)，k = (m+n)/2，奇数时找k+1大的数，偶数是找第k大和第k+1大的数再除2。

376.Wiggle Subsequence 摆动子序列（Medium）

376.Find the Celebrity 寻找名人（medium）

先设定候选人res为0，从1开始遍历数组，对于遍历到的人i，若候选人res认识i，则将候选人res设为i。第一次遍历完毕以后，再开始第二次遍历，来判断res是否确实为解。T: O(n), S: O(1)

19.Remove Nth Node From End of List 移除链表倒数第N个节点（medium）

解法1: two pass，先求出链表的总长度，然后在删除node

83. Remove Duplicates from Sorted List移除有序链表中的重复项（Easy）

移除有序链表中的重复项，返回新链表。定义1个指针指向链表的第一个元素，然后第一个元素和第二个元素比较，如果重复，则删掉第二个元素，如果不重复，指针指向第二个元素。

203.Remove Linked List Elements 移除链表元素 （Easy）

237.Delte Node in a Linked List 删除链表的节点（Easy）

解法：先把next节点的值赋给当前节点，在把当前节点的next变成当前节点的next.next。

61. Rotate List 旋转链表 （Medium）

要注意当k大于链表长度时的处理，需要先遍历一遍得到链表长度n，然后k对n取余，用余数来翻转。

92.Reverse Linked List II 反向链表 II （Medium）

先建立一个新list node: dummy，用dummy链接m之前不用反向的node，然后反向m~n的节点，最后在把反向的连接起来。

206.Reverse Linked List 反向链表（Easy）

反向链表，分别用递归和迭代方式实现。

递归Iteration：

新建一个node(value=任意值, next = None)， 用一个变量 next 记录head.next，head.next指向新node.next，新 node.next 指向head，next 进入下一个循环，重复操作，直到结束。

迭代Recursion：

2.Add Two Numbers 两个数字相加（Medium）

给定两个链表分别代表两个非负整数。数位以倒序存储，并且每一个节点包含一位数字。将两个数字相加并以链表形式返回。题目不难，主要考察链表操作和加法进位。

进位 = sum / 10，当前位值 = sum % 10

21.Merge Two Sorted Lists 合并有序链表（Easy）

解法1：dummy list，新建一个链表，然后两个链表中从头各取一个元素进行比较，小的写入新链表，直到结束，返回dummy.next。

解法2：recursion，代码简洁，但空间复杂度高O(n)

445. Add Two Numbers II 两个数字相加 II（Medium）

141. Linked List Cycle 链表中的环（Easy）

给定一个链表，判断是否有环存在。Follow up: 不使用额外空间。

解法：双指针，一个慢指针每次走1步，一个快指针每次走2步的，如果有环的话，两个指针肯定会相遇。

142. Linked List Cycle II 链表中的环 II（medium）

141. Linked List Cycle 的拓展，这题要返回环开始的节点，如果没有环返回null。

解法：双指针，还是用快慢两个指针，相遇时记下节点。

725.Split Linked List in Parts 拆分链表成部分（Medium）

思路：

第一次遍历单链表，求出链表的长度length；

求出平均分成的k个链表中，每个的结点avg，以及还多余的结点rem；

第二次遍历输入链表，如果达到avg，且rem存在值，则把本次遍历的结果赋值给结果数组；

86. Partition List 划分链表（medium）

给一个链表和一个x值，划分链表，把所有小于x值的节点都移到大于等于x值的前面，两部分的节点顺序不变。

解法：维护两个queue，一个存小于x值的，一个存大于等于x值的，最后在把两个连在一起。记得把大于等于的最后加上null。

707. Design Linked List 设计链表（Easy）

自己设计一个链表可以实现各种功能。

817. Linked List Components 链接列表组件 (Medium)

从左到右遍历链表依次，每遇到一个节点，就看看这个节点的数值在不在G中，并且这个节点的下一个节点是不是空（末尾），下一个节点值在不在G中。

如果当前的节点值在G中，而下一个节点是空或者节点值不在G中，那么就是一个新的分段呗。

876. Middle of the Linked List 找出链表的中间节点（Easy）

声明：本文采用的程序或者解法大部分借鉴了其他作者的思路，就不一一声明了，如果侵权，请联系删除。

203.Remove Linked List Elements 移除链表元素（Easy）

61. Rotate List 旋转链表（Medium）

新建一个node(value=任意值, next = None)，用一个变量 next 记录head.next，head.next指向新node.next，新 node.next 指向head，next 进入下一个循环，重复操作，直到结束。