Linked List Conclusion
本文蒐集
LeetCode 21: Merge Two Sorted Lists
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example:
Constraints:
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
l1andl2are sorted in non-decreasing order.
我的解答
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 and not l2:
return
elif not l1:
return l2
elif not l2:
return l1
else:
head = perv = None
if l1.val <= l2.val:
head = perv = l1
l1 = l1.next
else:
head = perv = l2
l2 = l2.next
while l1 and l2:
if l1.val <= l2.val:
perv.next = l1
l1 = l1.next
perv = perv.next
else:
perv.next = l2
l2 = l2.next
perv = perv.next
if not l1:
perv.next = l2
else:
perv.next = l1
return headLeetCode 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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Constraints:
- The number of nodes in each linked list is in the range
[1, 100]. 0 <= Node.val <= 9- It is guaranteed that the list represents a number that does not have leading zeros.
我的答案
# 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:
head1 = l1
head2 = l2
sum2 = 0
flag = 0
whichHead = 1
while l1 and l2:
sum2 = l1.val + l2.val + flag
if sum2 >= 10:
flag = 1
l1.val = l2.val = sum2 - 10
else:
flag = 0
l1.val = l2.val = sum2
l1 = l1.next
l2 = l2.next
if l2:
whichHead = 2
while l1 and flag:
sum1 = l1.val + flag
flag = 0
if sum1 >= 10:
l1.val = sum1 - 10
flag = 1
else:
l1.val = sum1
l1 = l1.next
if flag == 1:
perv = head1
while perv.next:
perv = perv.next
perv.next = ListNode(1)
while l2 and flag:
sum1 = l2.val + flag
flag = 0
if sum1 >= 10:
l2.val = sum1 - 10
flag = 1
else:
l2.val = sum1
l2 = l2.next
if flag == 1:
perv = head2
while perv.next:
perv = perv.next
perv.next = ListNode(1)
if whichHead == 2:
return head2
else:
return head1
# 誤解題意，原本題意更簡單= =
# l1_size = 0
# l2_size = 0
# head1 = l1
# head2 = l2
# while l1:
# l1 = l1.next
# l1_size += 1
# while l2:
# l2 = l2.next
# l2_size += 1
# if l1_size > l2_size:
# curr = head1
# index = l1_size - l2_size
# sum2 = 0
# flag = 0
# for i in range(index):
# curr = curr.next
# while curr:
# sum2 = curr.val + head2.val + flag
# if sum2 >= 10:
# flag = 1
# curr.val = sum2 - 10
# else:
# curr.val = sum2
# curr = curr.next
# head2 = head2.next
# return head1
# else:
# curr = head2
# index = l2_size - l1_size
# sum2 = 0
# flag = 0
# for i in range(index):
# curr = curr.next
# while curr:
# sum2 = curr.val + head1.val + flag
# if sum2 >= 10:
# flag = 1
# curr.val = sum2 - 10
# else:
# curr.val = sum2
# curr = curr.next
# head1 = head1.next
# return head2LeetCode 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:
Constraints:
- The 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(object):
def flatten(self, head):
if not head:
return
dummy = Node(0,None,head,None)
stack = []
stack.append(head)
prev = dummy
while stack:
root = stack.pop()
root.prev = prev
prev.next = root
if root.next:
stack.append(root.next)
root.next = None
if root.child:
stack.append(root.child)
root.child = None
prev = root
dummy.next.prev = None
return dummy.nextLeetCode 138: Copy List with Random Pointer
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.
Return the head of the copied linked list.
The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
val: an integer representing Node.val random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node. Your code will only be given the head of the original linked list.
Example:
Constraints:
0 <= n <= 1000-10000 <= Node.val <= 10000Node.randomisnullor is pointing to some node in the linked list.
我的解答
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
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)
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)LeetCode 61: Rotate List
Given the head of a linked list, rotate the list to the right by k places.
Example:
Constraints:
- The number of nodes in the list is in the range
[0, 500]. -100 <= Node.val <= 100- 0 <= k <= 2 * \(10^9\)
我的答案
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head:
return
count = 1
h = head
while head.next:
count += 1
head = head.next
k = k % count
if k == 0:
return h
else:
head.next = h
head = h
for i in range(count-k):
head = head.next
h = head
for i in range(count-1):
head = head.next
head.next = None
return h