This paper will introduce the basic disintegration ideas and classic problems of linked list algorithm. This paper not only pursues to write excellent linked list code, but also cares more about how to write bug-free linked list code within a limited time.
General ideas for solving linked list problems:
A linked list is a linear storage structure that uses discrete memory blocks and stores Pointers to the next memory block in each memory. Therefore, a linked list is a form of a linear list. Linked list problem is a kind of problem to investigate the basic coding ability. The characteristic of this kind of problem is that the solution is not complicated, but the difficulty is to prove the correctness of the solution and how to code. That is, to see if you can write bug-free code, and to see if you can prove the algorithm mathematically.
- Use graphic techniques to free up some brain space. Think about the problem by drawing several small-scale examples. If the problem requires more than three Pointers to solve, then the time cost of drawing is acceptable.
- By drawing a general case, think about the main body disintegration of the algorithm. Usually 3-5 nodes.
- In this case, it is more important not to code immediately, but to give a few special examples to verify that the general idea is robust in special scenarios, usually 0,1,2,3,4 linked list nodes, and whether the list Pointers at the head and tail nodes work properly.
- Must be patient, do not try to fast and submit code, linked list problem is to exercise your code review ability, the idea is very simple, the difficulty is to bear down, calm analysis. Trust me, you can always find the problem with the first code.
So what’s the general idea? This is a model, linked list problem algorithm ideas is so several, after the master can apply, mathematical proof to see a few typical cases, the real difficulty lies in coding, linked list problem is related to pointer operation, easy to make mistakes, write bug free is very not allow things, so the most important is to practice more.
Classical linked list problems:
- Design a singly linked list: This takes advantage of the sentry idea
class MyLinkedList:
def __init__(self):
Initializing a linked list with a sentry node that never stores data simplifies the condition reading of head and tail insertions in insert and delete operations, thus increasing speed. "" "
self.sb = ListNode(- 1)
self.le = 0
def get(self, index):
""" Gets a node in a linked list by index. "" "
head = self.sb.next
if index < 0 or index >= self.le or head == None:
return - 1
for i in range(index):
head = head.next
return head.val
def addAtHead(self, val):
Insert node at the position of the head node, sentry mind so that it does not read the non-null case. "" "
head = self.sb.next
self.sb.next = ListNode(val)
self.sb.next.next = head
self.le += 1
def addAtTail(self, val):
""" Insert node at the end """
tmp = self.sb
for i in range(self.le):
tmp = tmp.next
tmp.next = ListNode(val)
self.le += 1
def addAtIndex(self, index, val):
Inserts a node at the specified index.
if index < 0 or index > self.le :
return - 1
pre = self.sb
for i in range(index):
pre = pre.next
tmp = pre.next
pre.next = ListNode(val)
pre.next.next = tmp
self.le += 1
def deleteAtIndex(self, index):
""" Specify index position to delete node """
if index < 0 or index >= self.le:
return
pre = self.sb
for i in range(index) :
pre = pre.next
pre.next = pre.next.next
self.le -= 1
Copy the code- Check whether the list has rings
The classical three questions of two-pointer thought are: whether a linked list has a ring, the intersection of the list and the ring, and the length of the ring. Define two Pointers, start from the beginning, one takes 2 steps each time, the other takes one step, if the two intersect, there will be a ring, do not cross the pointer that takes two steps first to the tail, then the interpretation of acyclic.
class Solution(object):
def hasCycle(self, head):
if head is None or head.next is None:
return False
fast ,slow = head,head
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if slow == fast:
return True
return False
Copy the code- Determine the entry point of the ring
After the fast and slow Pointers meet, the fast Pointers point to the head node again, and the two Pointers start to move simultaneously, one step at a time. When they meet again, they are the entry points of the rings.
class Solution(object):
def detectCycle(self, head):
if head == None or head.next == None:
return None
fast = head.next.next
slow = head.next
whilefast ! =None andfast.next ! =None:
fast = fast.next.next
slow = slow.next
if fast == slow:
break
if fast == None or fast.next == None:
return None
fast = head
whilefast ! = slow: fast = fast.next slow = slow.nextreturn fast
Copy the code- Solve the length of the ring to find the meeting point, one pointer continues to move, each step, record the number of moves, the other pointer does not move, the number of encounters is the length. It’s easy. Imagine.
pass
Copy the codeSo the question is, are the first two algorithms correct, and how do you prove them mathematically? 1. When the slow pointer reaches the entry point of the ring,L1 represents the distance from head to the entry point, which is also the distance traveled by the slow pointer. This means that the fast pointer must reach the entry point of the ring, and the distance from the entry point is set as L2. I represents the number of steps that the slow pointer needs to take to catch up with the fast pointer. 3. Total steps of slow pointer of S1 code, and total steps of fast pointer of S2 code. 4. C is the circumference of the ring. If the fast and slow Pointers meet, then (S1+i-L1)mod C = (S2+2i-L1)mod C. L1 is subtracted to subtract the number of steps before entering the loop. The slow pointer followed I steps so the fast pointer actually took 2I steps. Therefore, this condition must be satisfied if the encounter is certain. After removing the influence of the number of steps before entering the ring, only the distance relative to the entry point of the ring after entering the ring can be seen as follows :S1 = L1, s2-L1 = NC + L2, where N is the number of circles already around the ring. I mod C = (NC+L2+2i) mod C = (NC+L2+2i) mod C = (L2 + I) mod C = 0,N = 0, we know that L2 < C, I must have a solution within the integer range, so the fast and slow Pointers must meet. Proof of entry point algorithm of ring: (4)=>(4)=>(m-n-1)L2+L2=s =>(M-n-1)L2+ P1+P2=L1+P1 <=> (m-n-1)L2+P2=L1 P1+P2=L2), which tells us that the length of the list excluding rings is equal to the length from the intersection to the first intersection plus the length of the rings.
- Find the intersection point of two lists. Two Pointers point to the heads of two lists, respectively. When you keep going forward, when you reach the tail, you return to the head of another list. The intersection of linked list, to must be short at the end of the first list, back to the long list of head, when the long list of Pointers to the end also, its length was has come a step closer to the number of nodes in the list are, as long chain table pointer back to a short list of the head, the two position alignment, the forward, eventually meet, is the intersection point.
class Solution(object):
def getIntersectionNode(self, headA, headB):
p1 ,p2 = headA,headB
whilep1 ! = p2: p1 = headBif p1 == None else p1.next
p2 = headA if p2 == None else p2.next
return p1
Copy the code- Delete the two Pointers of the NTH reciprocal node of the single linked list. One of them moves n steps first, and then the two Pointers move together. When the first pointer reaches the tail, the last pointer is the precursor node of the node to be deleted. The NTH to the last is actually the positive number L minus n plus 1,L is the length of the list, so L minus n is exactly the precursor to deleting the node. N steps, and then L-n, so that the second pointer is exactly at the L-n node.
class Solution(object):
def removeNthFromEnd(self, head, n):
pre ,last = head,head
for i in range(n):
pre = pre.next
if pre == None:
return head.next
whilepre.next ! =None:
pre = pre.next
last = last.next
last.next = last.next.next
return head
Copy the codeThe problem of pointer operation is to examine the boundary conditions of pointer operation, which requires coding ability.
- Single-linked list inversion two Pointers implementation C version:
class Solution(object):
def reverseList(self, head):
"" Use three Pointers to complete a single linked list operation. "" "
if head == None:
return None
pre = None
next = head.next
whilehead ! =None:
head.next = pre
pre = head
head = next
ifnext ! =None:
next = next.next
return pre
Copy the code- The boundary condition is considered when removing all elements with the value val in the list. The first loop is the key. The method of deleting val by traversing a list with 0,1,2, and 3 nodes is not suitable for the head nodes and the head nodes are successive Val nodes that need to be deleted.
class Solution(object):
def removeElements(self, head, val):
if head == None:
return None
whilehead ! =None and head.val == val:
if head.next == None:
return None
else:
head = head.next
pre = head
whilepre.next ! =None:
if pre.next.val == val:
pre.next = pre.next.next
else:
pre = pre.next
return head
Copy the code- The parity linked list moves forward by interleaving two Pointers next to each other, skillfully realizing the independent traversal of the parity nodes, and then connecting them independently and merging them. The difficulty is that pointer relations do not make a mistake, you can use drawing skills to assist thinking, linked list problems test programming ability, to calm down, patience check this is the key.
class Solution(object):
def oddEvenList(self, head):
if head is None:
return head
odd = head
even = head.next
if even is None:
return head
odd_prev = odd
even_prev = even
even_head = even
while even is not None and even.next is not None:
odd = even.next
even = odd.next
odd_prev.next = odd
even_prev.next = even
odd_prev = odd
even_prev = even
odd.next = even_head
return head
Copy the code- The fast and slow pointer of palindrome list finds the midpoint, reverses the second half of the list, traverses the list from the beginning to the midpoint again, and compares its value one by one to judge the palindrome. The emphasis here is on proper abstraction in the coding process, which can simplify the code logic and greatly improve the correctness and readability of the written code.
class Solution(object):
def isPalindrome(self, head):
if head is None or head.next is None:
return True
mid = self.getMid(head)
mid.next = self.getFanZhuan(mid.next)
p,q = head,mid.next
while q is not None and p.val == q.val:
q = q.next
p = p.next
self.getFanZhuan(mid.next)
return q == None
def getMid(self,head):
fast,slow = head.next,head
while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
return slow
def getFanZhuan(self,head):
if head is None or head.next is None:
return head
pre,curr,next = None,head,head.next
while curr is not None:
curr.next = pre
pre = curr
curr = next
next = None if next is None else next.next
return pre
Copy the code- Double linked list design Double linked list design is a little bit more complicated than a single linked list, but if you want to understand the sentry in a linked list, it’s pretty easy, but I did this problem for three days, and I do this problem every morning at 7:30. I think it took about 40 minutes, but I’m a little bit crazy, and when you’re designing data structures, you have to write multiple methods, and when you review code, you have to consider the effect of multiple functions calling each other, Class-level “invariants” require deep thinking about the role of each behavior, a careful understanding of the pre – and post-conditions under which each behavior occurs, and what is a constant state to be maintained throughout the life of an object.
class MyLinkedList(object):
def __init__(self):
""" Initialize your data structure here. """
self.head = ListNode(- 1)
self.tail = ListNode(- 1)
self.head.next = self.tail
self.tail.prev = self.head
self.length = 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.length:
return - 1
return self.getNode(index).val
def getNode(self,index):
frist = self.head.next
for i in range(index):
frist = frist.next
return frist
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: void """
frist = self.head.next
node = ListNode(val)
self.head.next = node
node.prev = self.head
node.next = frist
frist.prev = node
self.length += 1
def addAtTail(self, val):
""" Append a node of value val to the last element of the linked list. :type val: int :rtype: void """last = self.tail.prev node = ListNode(val) self.tail.prev = node node.next = self.tail last.next = node node.prev = last self.length +=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: void """
if index < 0 or index > self.length:
return
if index == self.length:
self.addAtTail(val)
returnold = self.getNode(index) node = ListNode(val) pre = old.prev pre.next = node node.prev = pre node.next = old old.prev = node self.length +=1
def deleteAtIndex(self, index):
""" Delete the index-th node in the linked list, if the index is valid. :type index: int :rtype: void """
if index < 0 or index >= self.length:
return
node = self.getNode(index)
pre = node.prev
next = node.next
pre.next = next
next.prev = pre
node.next = None
node.prev = None
self.length -= 1
Copy the code- Concatenating two ordered lists The key to this problem is the handling of exceptions where both input lists may be empty and may be of different lengths. They all need to be handled separately
class Solution(object):
def mergeTwoLists(self, l1, l2):
if l1 is None and l2 is None:
return None
elif l1 is None:
return l2
elif l2 is None:
return l1
sb ,headA,headB = ListNode(- 1),l1,l2
headSB = sb
while headA and headB :
if headA.val > headB.val:
sb.next = headB
headB = headB.next
elif headA.val < headB.val:
sb.next = headA
headA = headA.next
else:
sb.next = headA
headA = headA.next
sb = sb.next
sb.next = headB
headB = headB.next
sb = sb.next
if headA:
sb.next = headA
elif headB:
sb.next = headB
return headSB.next
Copy the code- Adding two numbers represented in reverse lists this problem simplifies the code by using sentinels, while keeping an eye on the carry, which is very easy to do.
class Solution(object):
def addTwoNumbers(self, l1, l2):
rem = 0
dummy = ListNode(0)
p = dummy
while l1 or l2 or rem:
s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + rem
rem = s/10
p.next = ListNode(s%10)
p = p.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
Copy the code- Flat multilevel bidirectional linked listsLet me explainhereIf there is no child list, it will continue to be traversed. The whole program is completed in a loop. The son list traversing the child table, head and tail of the list of Pointers, child list of the next end node pointer to subject list current next, if the next is not empty, it is prev Pointers point to the end node of the linked list, and then again to update the head of the linked list node, make its traverse the nodes of the current main chain table next pointer pointing to the list The prev pointer to the head of the child lists points to it in reverse, and the pointer to the children is assigned to None, and the current pointer points directly to next of the tail pointer of the merged child lists to reduce the number of traversals. Reciprocating iteration, specific can be understood according to the code, drawing. This topic is more complex in the pointer, drawing the analysis of assignment, is to write
bug freeThe key.
class Solution(object):
if not head:
return None
p = head
while p:
if not p.child:
p = p.next
continue
p1 = p.child
p2 = p.child
while p2.next:
p2 = p2.next
p2.next = p.next
if p.next:
p.next.prev = p2
p.next = p1
p1.prev = p
p.child = None
p = p1
return head
Copy the code- Copying a linked list with a random pointer This topic is the key to understand the random pointer. When copying nodes, the replication of the random pointer is relative, so it must ensure that the node to which the random pointer points is relatively unchanged. Click here for details
class Solution(object):
def copyRandomList(self, head):
if not head:
return None
p = head
while p:
tmp = RandomListNode(p.label)
tmp.next = p.next
p.next = tmp
p = tmp.next
p = head
while p:
if p.random:
p.next.random = p.random.next
p = p.next.next
n,o = head.next,head
new = n
while n:
o.next = n.next
o = o.next
if not o:
break
n.next = o.next
n = n.next
return new
Copy the code- The best way to solve this problem is to do it in linear time in constant space. First, reverse the whole sequence, and then reverse the two parts respectively when finding the partition point. Note that the tail pointer must be specified in reverse order, because lists are continuous
class Solution(object):
def rotateRight(self, head, k):
if head is None:
return None
if k == 0:
return head
count = 0
end = None
tmp = head
while tmp:
tmp = tmp.next
count += 1
head = self.nx(head,end)
k = k % count
tmp = head
whilek ! =0:
tmp = tmp.next
k -= 1
end = tmp
new_head = self.nx(head,end)
head.next = self.nx(end,None)
return new_head
def nx(self,head,end):
if head is None:
return None
pre,curr,next = None,head,head.next
whilecurr ! = end: curr.next = pre pre = curr curr = next next = next.nextif next else None
return pre
Copy the code- The nature of this problem is to investigate the relationship between linear structure and tree structure. How to use linear structure to store a binary search tree? An ordered linear list can be an array or a linked list. In this case, how to construct a binary search tree from an ordered linear list? Dichotomy is the key. Dichotomy is the mapping between ordered linear list and binary search. So how to pick the middle point of dichotomy? Array can calculate index index, linked list can use fast or slow pointer,ok now the problem is solved, look at the code.
class Solution(object):
def sortedListToBST(self, head):
return self.insterC(head,None)
def insterC(self,head,tail):
if head is tail:
return None
if head.next is tail:
return TreeNode(head.val)
fast = mid = head
while fast is not tail and fast.next is not tail:
mid = mid.next
fast = fast.next.next
tree = TreeNode(mid.val)
tree.left = self.insterC(head,mid)
tree.right = self.insterC(mid.next,tail)
return tree
Copy the code- Swap nodes in a linked list in pairsThis topic is similar to the idea of reverse order of linked list, but as long as we correctly understand the relationship of linked list Pointers, pay attention to the transformation of precursor, current node, and successor. Note the check code, the check of boundary conditions, the analysis of exceptions can be written
bug freeIt’s all about patience and keeping your cool.details
class Solution(object):
def swapPairs(self, head):
if head is None:
return head
sb = ListNode(- 1)
sb.next = head
a = sb
b = head
c = head.next
while c:
a.next = c
b.next = c.next
c.next = b
a = b
b = b.next
if b is None:
break
c = b.next
return sb.next
Copy the code- Sorting list This problem is essentially linked list implementation of merge sort, topic request O (nlong), linked list implementation merge sort of advantage is can be done under constant space merge, the disadvantage is that the query point can’t wanted to array in a constant time to complete, so their performance is slower than the array form some, but also in the same order of magnitude, and does not require space for storage, and additional Space, in some cases, is also a good choice. details
class Solution(object):
def sortList(self, head):
if head is None or head.next is None :
return head
mid = self.getMid(head)
left = self.sortList(head)
right = self.sortList(mid)
return self.merge(left,right)
def getMid(self,head):
m,k = head,head
sb = ListNode(- 1)
sb.next = head
while k and k.next:
k = k.next.next
m = m.next
sb = sb.next
sb.next = None
return m
def merge(self,a,b):
sb = ListNode(- 1)
curr = sb
while a and b:
if a.val >= b.val:
curr.next = b
b = b.next
else:
curr.next = a
a = a.next
curr = curr.next
if a:
curr.next = a
elif b:
curr.next = b
return sb.next
Copy the code- Rearranging lists is a combination of three common linked list behaviors: fetching list midpoints, reversing linked lists, and cross-merging linked lists.
class Solution(object):
def reorderList(self, head):
if not head or not head.next:
return
if not head.next.next:
return
mid = self.get_mid(head)
head1 = self.nx(mid)
head = self.marge(head,head1)
def get_mid(self,head):
pre = ListNode(- 1)
pre.next = head
fast,slow = head,head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
pre = pre.next
pre.next = None
return slow
def nx(self,head):
pre, cur, next = None,head,head.next
while cur:
cur.next = pre
pre = cur
cur = next
if next:
next = next.next
return pre
def marge(self,head1,head2):
dummy = ListNode(- 1)
d = dummy
p, q = head1,head2
while p and q:
d.next = p
p = p.next
d = d.next
d.next = q
q = q.next
d = d.next
if q:
d.next = q
elif p:
d.next = p
return dummy.next
Copy the code- The key of the linked list component understanding problem is to define the concept of components, which can be solved by using the characteristics of map key and determine the counting strategy. The key of this problem is to understand the new concept correctly, and identify the classic pattern – set search algorithm.
class Solution:
def numComponents(self, head, G):
if head is None or len(G) == 0:
return 0
count = 0
cur = head
GMap = {}
for v in G:
GMap[v] = 0
while cur:
if cur.val in GMap and (cur.next is None or cur.next.val not in GMap):
count += 1
cur = cur.next
return count
Copy the code- Separated list 01 is solved in two steps. The first step is to find the partition rule. Second, divide according to rules. The rule is very simple according to the problem, it’s split first and then split the remainder and the problem is to find the rule, mathematically express it and encapsulate the behavior.
class Solution:
def splitListToParts(self, root, k):
p = root
size = 1
while p and p.next:
size += 1
p = p.next
mod = size % k
num = int(size / k)
res = []
tmp = root
whilek ! =0:
ifmod ! =0:
root = self.splitListNodeByLen(tmp,num+1)
mod -= 1
else:
root = self.splitListNodeByLen(tmp,num)
res.append(tmp)
tmp = root
k -= 1
return res
def splitListNodeByLen(self,root,l):
if not root or l <= 0:
return root
pre = None
while l > 0:
pre = root
root = root.next
l -= 1
pre.next = None
return root
Copy the code- Two Numbers together II this topic is the upgrade version of the table together, even the table no longer reverse need to deal with, the collapse of the model is more general to the specific approach first, the solution to this problem I is bad, no best practice for reference, just I want to come out, since can’t from the beginning of the low, and operational problems, thought of using this auxiliary stack structure to handle directly. But it introduces additional complexity in the interim, and you can figure out how to optimize it later.
class Solution:
def addTwoNumbers(self, l1, l2):
s1, s2 = [], []
tmp1 ,tmp2 = l1, l2
while tmp1:
s1.append(tmp1.val)
tmp1 = tmp1.next
while tmp2:
s2.append(tmp2.val)
tmp2 = tmp2.next
c = 0
node = ListNode(- 1)
root = node
whilelen(s1) ! =0 andlen(s2) ! =0:
num = s1[- 1] + s2[- 1] + c
s1 = s1[:len(s1)- 1]
s2 = s2[:len(s2)- 1]
if num >= 10:
node.val = num - 10
c = 1
else:
node.val = num
c = 0
if len(s1) == 0 and len(s2) == 0:
if c == 1:
node.next = ListNode(- 1)
node = node.next
node.val = c
break
node.next = ListNode(- 1)
node = node.next
whilelen(s1) ! =0:
num = s1[- 1] + c
if num >= 10:
node.val = num - 10
c = 1
else:
node.val = num
c = 0
s1 = s1[:len(s1)- 1]
if len(s1) == 0:
if c == 1:
node.next = ListNode(- 1)
node = node.next
node.val = c
break
node.next = ListNode(- 1)
node = node.next
whilelen(s2) ! =0:
num = s2[- 1] + c
if num >= 10:
node.val = num - 10
c = 1
else:
node.val = num
c = 0
s2 = s2[:len(s2)- 1]
if len(s2) == 0:
if c == 1:
node.next = ListNode(- 1)
node = node.next
node.val = c
break
node.next = ListNode(- 1)
node = node.next
return self.nx(root)
def nx(self,root):
if root is None:
return None
pre = None
next = root.next
while root:
root.next = pre
pre = root
root = next
if next:
next = next.next
return pre
Copy the code- This problem is the implementation of a linked list in a quicksort partition.
class Solution:
def partition(self, head, x):
h1,h2 = ListNode(- 1),ListNode(- 1)
dummy = ListNode(- 1)
dummy.next = head
pre = dummy
tmp1,tmp2 = h1,h2
while pre and pre.next:
tmp = pre.next
pre.next = None
pre = tmp
if tmp.val >= x:
tmp1.next = tmp
tmp1 = tmp1.next
else:
tmp2.next = tmp
tmp2 = tmp2.next
tmp2.next = h1.next
return h2.next
Copy the code- Reverse linked list II this problem pointer more drawing aid more efficient.
class Solution:
def reverseBetween(self, head, m, n):
count = 0
dummy = ListNode(- 1)
pre = dummy
pre.next = head
while count < m- 1:
pre = pre.next
count += 1
last = pre
while count < n:
last = last.next
count += 1
cur = pre.next
next = last.next
self.reverse(cur, last)
pre.next = last
head = dummy.next
cur.next = next
return head
def reverse(self, cur,last):
last.next = None;
pre = None
next = cur.next
while cur:
cur.next = pre
pre = cur
cur = next
if next:
next = next.next
Copy the code- Add the two numbers using the sentinel pattern
class Solution(object):
def addTwoNumbers(self, l1, l2):
"" "" ""
rem = 0
dummy = ListNode(0)
p = dummy
while l1 or l2 or rem:
s = (l1.val if l1 else 0) + (l2.val if l2 else 0) + rem
rem = s/10
p.next = ListNode(s%10)
p = p.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
Copy the code- Plus One Linked List(1) leetCode If no such number is found, all numbers are 9. Create a new node with a value of 0 at the top of the table, increment by 1, and set all numbers on the right to 0. For example:
For example, 1->2->3, then the first digit that is not 9 is 3, add 1 to 3, become 4, there is no node on the right side, so do not do processing, return 1->2->4.
For example, 8->9->9, find the first digit that is not 9 is 8, add 1 to become 9, and then set the following digits to 0, get 9->0->0.
If 9->9->9 is not found, create a new node with a value of 0 in front, add 1 to become 1, set all the following digits to 0, get 1->0->0->0 ->0.
class Solution {
public:
ListNode* plusOne(ListNode* head) {
ListNode *cur = head, *right = NULL;
while (cur) {
if(cur->val ! =9) right = cur;
cur = cur->next;
}
if(! right) { right =new ListNode(0);
right->next = head;
head = right;
}
++right->val;
cur = right->next;
while (cur) {
cur->val = 0;
cur = cur->next;
}
returnhead; }};Copy the code-
Design Phone Directory Here, speak clearly, need not I said again, the design of the main investigation data structure, in fact, this kind of question first according to the experience to the most common structure can meet the requirements, the deficiencies are trying combination data structure, the key is to define what information do you want to know to make you one step closer to the right answer, it takes practice and summary.
-
Remove the key from a Binary Search Tree to Sorted Doubly-linked List. A very classic problem,LeetCode charges, there is no way to OJ, the local only go environment. So I wrote a solution in terms of go.
This problem uses divide and conquer idea, recursive realization. The pattern of the original problem can be seen as: left subtree loop merging with root loop merging with right subtree loop merging. Thus, the subproblem is: 1. “left subtree root right subtree” ring,2. A merger. The recursion base is obviously null and returns directly. The recursive part is: left, right ring. Each recursion does just that: join the root into a loop, and merge the left root and right rings. The merge action is a function of joining two circular lists into a linked list.
type TreeNode struct {
Left *TreeNode
Right *TreeNode
Val int
}
func BST2DLL(root *TreeNode) *TreeNode {
if root == nil{
return nil} aLast := BST2DLL(root.Left) bLast := BST2DLL(root.Right) root.Left = root root.Right = root aLast = Append(aLast,root) aLast = Append(aLast,bLast)return aLast
}
func Append(a,b *TreeNode) *TreeNode {
if a == nil{
return b
}
if b == nil{
return a
}
aLast := a.Left
bLast := b.Left
Join(aLast, b)
Join(bLast, a)
return a
}
func Join(a, b *TreeNode) {
a.Right = b
b.Left = a
}
Copy the code30. The problem of Insert into a Cyclic Sorted List to Insert nodes into a Cyclic Sorted List is an analysis of various situations. The first problem is that when the List is empty, the Insert value is between the maximum and minimum, less than the minimum or greater than the maximum. Consider the different situations. I’m going to follow the number line. 31. A set of k flip linked lists uses the sentry to reduce pointer operations, and uses K as a counter to control the pre,left, and right boundary Pointers for operation. Flip the linked list by moving the pointer to the correct position according to the counter. The method is clumsy but simple and effective haha, I will optimize it later. Now I will try my best to practice the basic model by seeing more types and collecting more data.
class Solution:
def reverseKGroup(self, head, k):
""" :type head: ListNode :type k: int :rtype: ListNode """
if k <= 0 or not head or not head.next:
return head
dummy = ListNode(- 1)
dummy.next = head
cur = head
pre = dummy
while cur:
left,right = cur,cur
for i in range(k- 1):
cur = cur.next
if cur is None:
return dummy.next
right = cur
self.nx(pre,left,right)
cur = left
pre = left
cur = cur.next
return dummy.next
def nx(self,pre,l,r):
if not pre or not l or not r or l == r:
return l
p ,cur,next = pre,l,l.next
tmp = r.next
whilecur ! = tmp: cur.next = p p = cur cur = nextif next:
next = next.next
pre.next = p
l.next = tmp
Copy the code32. Merge K sorted lists this problem can be done very nicely, but I will give you an intuitive brute force solution, which will be improved in the future. This problem can be understood as: select the largest node from the list each time, remove it from the list and use sentinels to form new nodes, then update the linked list, continuously drop generations, and finally end when the list is empty.
class Solution:
def mergeKLists(self, lists):
""" :type lists: List[ListNode] :rtype: ListNode """
dummy = ListNode(- 1)
cur = dummy
whilelen(lists) ! =0:
index = self.min(lists)
if not lists[index]:
del lists[index]
continue
cur.next = lists[index]
if lists[index] and lists[index].next:
lists[index] = lists[index].next
else:
del lists[index]
cur = cur.next
return dummy.next
def min(self,lists):
m = lists[0]
index = 0
i = 1
while i<len(lists):
if lists[i] and m and m.val > lists[i].val:
m = lists[i]
index = i
i += 1
return index
Copy the code33. The idea of deleting a node from a linked list is clever. You only have a given node and no pointer to a precursor node. Ingenious use of the idea of assignment to solve.
class Solution:
def deleteNode(self, node):
""" :type node: ListNode :rtype: void Do not return anything, modify node in-place instead. """
tmp = node.next
node.next = node.next.next
tmp.next = None
node.val = tmp.val
Copy the code34. The middle node of the linked list was originally placed in the first order, but it was found that it was not written, so I added it here. As mentioned many times before, intermediate nodes, fast or slow Pointers
class Solution(object):
def middleNode(self, head):
""" :type head: ListNode :rtype: ListNode """
if not head and not head.next:
return head
slow,fast = head,head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
Copy the code