Like attention, no more lost, your support means a lot to me!

šŸ”„ Hi, I’m Chouchou. GitHub Ā· Android-Notebook has been included in this article. Welcome to grow up with Chouchou Peng. (Contact information at GitHub)

preface

  • Questions related to linked lists are frequently asked in interviews and are often the basis for solving other complex problems.
  • In this article, I will comb through the problems & solutions of linked list problems. Please be sure to like and follow if you can help, it really means a lot to me.

series

  • The algorithm of interview questions | problems summary list”
  • The algorithm problem of intersection and cyclization interview questions | chain table”
  • The interview questions | back algorithm problem solving framework
  • Interview questions | and check the data structure set & joint – search algorithms,
  • The interview questions | binary tree data structure foundation”

Extension of the article

  • Algorithm of interview questions | buildings with eggs (from Google interview questions)
Delete the linked list node Hint & problem solving
203. Remove linked list elements

Remove Linked List Elements		 “Antithesis”
237. Delete a node from a linked list

Delete Node in a Linked List		 “Antithesis”
Delete the penultimate node of the linked list

Remove Nth Node From End of List		 “Antithesis”
86. Separate linked lists

Partition List		 “Antithesis”
328. Odd-even linked lists

Odd Even Linked List		 “Antithesis”
83. Delete duplicate elements from sorted linked lists

Remove Duplicates from Sorted List
Delete duplicate element II from sorted list

Remove Duplicates from Sorted List II
725. Separated linked lists

Split Linked List in Parts
(Extended) 0876. Intermediate node of a linked list

Middle of the Linked List		 “Antithesis”


Reverse a linked list Hint & problem solving
206. Reverse linked lists

Reverse Linked List		 “Antithesis”
92. Reverse linked list II

Reverse Linked List II		 “Antithesis”
234. Palindrome linked list

Palindrome Linked List		 “Antithesis”
25. Flip linked lists in groups of K

Reverse Nodes in k-Group


Merge ordered linked lists Hint & problem solving
21. Merge two ordered lists

Merge Two Sorted Lists		 “Antithesis”
Merge K ascending linked lists

Merge k Sorted Lists		 “Antithesis”


Sorting list Hint & problem solving
Insert sort on linked lists

Insertion Sort List		 “Antithesis”
148. Sort linked lists

Sort List		 “Antithesis”


Circular linked list Hint & problem solving
160. Intersecting linked lists

Intersection of Two Linked Lists		 “Antithesis”
141. Circular linked lists

Linked List Cycle		 “Antithesis”
142. Circular linked List II

Linked List Cycle II		 “Antithesis”
61. Rotate linked lists

Rotate List		 “Antithesis”


other Hint & problem solving
Swap nodes in a linked list in pairs

Swap Nodes in Pairs
143. Rearrange linked lists

Reorder List
138. Copy linked lists with random Pointers

Copy List with Random Pointer
380. Constant time inserts, deletes, and retrieves random elements

Insert Delete GetRandom O(1)
381. O(1) Time to insert, remove and get random elements – allow repetition

Insert Delete GetRandom O(1) – Duplicates allowed
707. Design linked lists

Design Linked List
430. Flat multilevel bidirectional linked lists

Flatten a Multilevel Doubly Linked List
817. List components

Linked List Components		 “Antithesis”

directory

1. An overview of the

1.1 Definition of linked lists

Linked list is a common basic data structure, is a linear list. Unlike a sequential list, each node in a linked list is not stored sequentially, but is pointed to the next node through the node’s pointer field.

1.2 Advantages and disadvantages of linked lists

contrast advantages disadvantages
Memory management Make full use of computer memory space, more flexible allocation of memory space Pointer fields increase memory consumption
Operational efficiency Can be in
O ( 1 ) O(1) Delete or add nodes within time (if the precursor node is known)		 Lost the random access feature of the array, the query corresponding to the location of the node needed
O ( n ) O(n) time
Data capacity The memory must be allocated in advance. If the memory capacity is insufficient, the capacity must be expanded No pre-allocated memory space is required, and no expansion is required
Access performance / CPU caching rows does not improve efficiency

1.3 Types of linked lists

Single, double, circular, and static lists

2. Delete linked list nodes

When deleting a linked list node, considering that it may be the first node of the list to be deleted (no precursor node), a sentinel node can be added for coding convenience. Among them, in the problem of deleting the penultimate node of the linked list, using fast and slow Pointers to find the penultimate node in a scan is an important programming skill.

237. Delete Node in a Linked ListĀ “Antithesis”
Remove Linked List ElementsĀ “Antithesis”
Class Solution {fun removeElements(head: ListNode? , `val`: Int): ListNode? {// val sentinel = ListNode(-1). Next = head var pre = sentinel var cur: ListNode? = sentinel while (null ! = cur) {if (' val '== cur.' val ') {// Remove pre. Next = cur.next} else {pre = cur} cur = cur.next} return sentinel Class Solution {fun removeElements(head: ListNode? , `val`: Int): ListNode? {// val sentinel = ListNode(-1). Next = head var pre = sentinel var cur: ListNode? = sentinel while (null ! = cur) {val removeNode = if (' val '== cur.' val ') {// Remove pre. Next = cur.next cur else {pre = cur null} cur = cur.next if (null ! = removeNode) { removeNode.next = null } } return sentinel.next } }Copy the code
Remove the Nth Node From End of ListĀ “Antithesis”

Given a linked list, delete the NTH last node of the list and return the first node of the list.

class Solution { fun removeNthFromEnd(head: ListNode, n: Int): ListNode? {// val sentinel = ListNode(-1) sentinel. Next = head var fast: ListNode? = sentinel var slow: ListNode? = sentinel for (index in 0 until n) { fast = fast!! .next} // Find the last KTH node while (null! = fast!! .next) { fast = fast.next slow = slow!! .next } slow!! .next = slow.next!! .next return sentinel.next } }Copy the code

Complexity analysis:

  • Time complexity: Scan each node once, and the time complexity is O(n)O(n)O(n)
  • Space complexity: Constant level variables are used and the space complexity is O(1)O(1)O(1)

In a similar way, the Middle of the Linked List is found by using fast and slow Pointers:

class Solution { fun middleNode(head: ListNode?) : ListNode? { if (null == head || null == head.next) { return head } var fast = head var slow = head while (null ! = fast && null ! = fast.next) { fast = fast.next!! .next slow = slow!! .next } return slow } }Copy the code
86. Partition List separates linked listsĀ “Antithesis”

Deletes all nodes in the linked list that are equal to the given value val.

To separate a linked list, you must first remove a node greater than or equal to val from the original list and then join the two lists.

class Solution { fun partition(head: ListNode? , x: Int): ListNode? {if (null == head) {return null} val sentinel = ListNode(-1) sentinel.next = head var pre = sentinel // second linked list var bigHead : ListNode? = null var bigRear = bigHead var cur = head while (null ! If (cur. 'val' >= x) { Next if(null == bigHead){bigHead = cur bigRear = cur}else{bigRear!! .next = cur bigRear = cur}} else {pre = cur} if (null == cur.next) {// splice. pre = bigHead bigRear? .next = null break } cur = cur.next } return sentinel.next } }Copy the code

Complexity analysis:

  • Time complexity: Scan each node once, and the time complexity is O(n)O(n)O(n)
  • Space complexity: Constant level variables are used and the space complexity is O(1)O(1)O(1)
328. Odd Even Linked ListĀ “Antithesis”

An odd-even list consists of placing odd nodes in one list, even nodes in another list, and then attaching even nodes to the end of the odd-even list

class Solution { fun oddEvenList(head: ListNode?) : ListNode? { if (null == head) { return null } var odd: ListNode = head var even = head.next val evenHead = even while (null ! = even && null ! = even.next) {// Even.next = even.next odd = odd.next!! Next = even.next = even.next = even.next = even.next = even.next = evenHeadCopy the code
Delete Duplicates from Sorted List
Delete Duplicates from Sorted List II. Delete Duplicates from Sorted List II

3. Reverse the list

Reverse linked list questions appear very frequently in the interview, I believe that students who have several interview experience will agree with this point of view. Here, I’ve identified four reverse linked list problems, ranging from easy to hard.

206. Reverse Linked ListĀ “Antithesis”

Reverse a single linked list.

Solution 1: Recursion

class Solution { fun reverseList(head: ListNode?) : ListNode? { if(null == head || null == head.next){ return head } val prefix = reverseList(head.next) head.next.next = head head.next = null return prefix } }Copy the code

Complexity analysis:

  • Time complexity: Scan each node once, and the time complexity is O(n)O(n)O(n)
  • Space complexity: The recursive stack is used and the space complexity is O(n)O(n)O(n)

Solution 2: Iteration

class Solution { fun reverseList(head: ListNode?) : ListNode? { var cur: ListNode? = head var headP: ListNode? = null while (null ! = cur) { val tmp = cur.next cur.next = headP headP = cur cur = tmp } return headP } }Copy the code

Complexity analysis:

  • Time complexity: Scan each node once, and the time complexity is O(n)O(n)O(n)
  • Space complexity: Constant level variables are used and the space complexity is O(1)O(1)O(1)
92. Reverse Linked List IIĀ “Antithesis”

Given a linked list, rotate the list by moving each node of the list k positions to the right, where k is non-negative.

class Solution { fun reverseBetween(head: ListNode? , m: Int, n: Int): ListNode? {if (null = = head | | null = = head. The next) {return head} / / sentinel node val sentinel = ListNode (1) sentinel. Next = head var rear = sentinel // 1. Var cur = sentinel for (index in 0 until m-1) {cur = cur.next!! Rear = cur} // 2. ReverseList (rear. Next!! , n-m + 1) return sentinel. Next} /** * reverse specified area * @param size */ fun reverseList(head: ListNode, size: Int): ListNode? { var cur: ListNode? = head var headP: ListNode? Val headTemp = head var count = 0 while (null! = cur.next cur.next = headP headP = cur = TMP count++} // connect to the NTH node headtemp.next  = cur return headP } }Copy the code

Complexity analysis:

  • Time complexity: Scan each node once, and the time complexity is O(n)O(n)O(n)
  • Space complexity: Constant level variables are used and the space complexity is O(1)O(1)O(1)
234. Palindrome Linked ListĀ “Antithesis”

Determine if a linked list is palindromic.

Use the fast and slow pointer to find the middle node, reverse the last part of the list (based on reverse list II), compare whether the first and second parts of the list are the same, and finally reverse back to the original list.

class Solution { fun isPalindrome(head: ListNode?) : Boolean { if (null == head || null == head.next) { return true } // 1. Var fast = head var slow = head while (null! = fast && null ! = fast.next) { slow = slow!! .next fast = fast.next!! ReverseP = reverseList(slow!!) Var p = head var q: ListNode? = reverseP var isPalindrome = true while (null ! = p && null ! = q) { if (p.`val` == q.`val`) { p = p.next q = q.next } else { isPalindrome = false break } } // 4. Return isPalindrome} /** * private fun reverseList(head: ListNode): ListNode {// omitted, see the previous section... }}Copy the code

Complexity analysis:

  • Time complexity: Scans each node twice, and the time complexity is O(n)O(n)O(n) O(n)
  • Space complexity: Constant level variables are used and the space complexity is O(1)O(1)O(1)
Reverse Nodes in k-group Reverse Nodes in k-group

You are given a linked list, each k nodes in a group of flipped, please return to the flipped list.

4. Merge ordered lists

Merge ordered list questions appear in the interview frequency is high, among them, merge two ordered list is relatively simple, and its advanced version merge K ascending list factors to consider more comprehensive, the difficulty has also increased, come to try it.

21. Merge Two Sorted ListsĀ “Antithesis”

Merges two ascending lists into a new ascending list and returns. A new list is formed by concatenating all the nodes of a given two lists.

class Solution { fun mergeTwoLists(l1: ListNode? , l2: ListNode?) : ListNode? {if (null == L1) return l2 if (null == L2) return L1 // Sentinel node val sentinel = ListNode(-1) var rear = sentinel var p = L1  var q = l2 while (null ! = p && null ! = q) { if (p.`val` < q.`val`) { rear.next = p rear = p p = p.next } else { rear.next = q rear = q q = q.next } } rear.next = if (null ! = p) p else q return sentinel.next } }Copy the code

Complexity analysis:

  • Time complexity: Scan each node once. The time complexity is O(m+ N)O(M + N)O(M + N)O(m+ N).
  • Space complexity: Constant level variables are used and the space complexity is O(1)O(1)O(1)
23. Merge K Sorted Lists Merge K ascending ListsĀ “Antithesis”

You are given an array of linked lists, each of which has been sorted in ascending order. Please merge all lists into one ascending list and return the merged list.

Solution 1: Violence

Idea 1: Similar to merging two ordered lists, remove the smallest node from k lists in each round and insert it into the resulting list. Where, the time complexity of extracting the minimum node from the number of K is O(k)O(k)O(k).

Train of thought 2: This train of thought is similar to the last train of thought, with the same time complexity and space complexity page, namely: merge k linked lists and result linked lists in turn.

slightlyCopy the code

Complexity analysis:

  • Time complexity: O(NK * K)O(NK * K)O(NK āˆ— K)
  • Space complexity: O(1)O(1)O(1)

Solution 2: Sorting

After storing all the nodes in an array, do a quick sort, and then output the array to a single linked list.

class Solution { fun mergeKLists(lists: Array<ListNode? >): ListNode? { if (lists.isNullOrEmpty()) { return null } // 1. Val array = ArrayList<ListNode>() for (list in lists) {var cur = list while (null! = cur) { array.add(cur) cur = cur.next } } // 2. SortWith (Comparator {node1, node2 -> node1. 'val' - node2. 'val'}) // 3. Val newHead = ListNode(-1) var rear = newHead for (node in array) {rear. Next = node rear = node} return newHead.next } }Copy the code

Complexity analysis:

  • Time complexity: Merge node time O(NK)O(NK)O(NK)O, quick sort time O(NK āˆ— LGNK)O(NK * LGNK)O(NK āˆ— LGNK)O(NK * LGNK)O, output single linked list time O(NK)O(NK)O(NK)O, Total time complexity O(NK * LGNK)O(NK * LGNK)O(NK āˆ— LGNK)
  • Space complexity: Using array space O(nk)O(nk)O(nk)

Solution 3: merge

Split the k-list into two parts, then recursively process the two sets of lists, and finally merge them.

Class Solution {// Merge k ordered lists fun mergeKLists(Lists: Array<ListNode? >): ListNode? { if (lists.isNullOrEmpty()) { return null } return mergeKLists(lists, 0, lists.size - 1) } fun mergeKLists(lists: Array<ListNode? >, left: Int, right: Int): ListNode? {if (left == right) {return lists[left]} val mid = (left + right) ushr 1 return mergeTwoLists( MergeKLists (Lists, left, mid), mergeKLists(Lists, mid + 1, Right))} , l2: ListNode?) : ListNode? {// skip, see previous section... }}Copy the code

Complexity analysis:

  • Time complexity: Time is mainly in the operation of merging linked lists. It can be seen from the recursive tree that the number of nodes at each level of the recursive tree is NKNKNK, and the height of the recursive tree is H = LGKH = LGK, so the total time complexity is O(NK āˆ— LGK)O(NK * LGK)O(NK āˆ— LGK)
  • Space complexity: Using a recursive stack, the space complexity is O(LGK)O(LGK)O(LGK)

Solution 4: small top stack method

In solution 1, the time complexity of removing the smallest node from the number of K is O(k)O(k)O(k) O(k), and the minimum heap (priority queue) can be used to optimize to O(LGK)O(LGK)O(LGK). Where the in-heap node is always the head of the unprocessed portion of the K linked list.

Class Solution {// Merge k ordered lists fun mergeKLists(Lists: Array<ListNode? >): ListNode? {if (lists. IsNullOrEmpty ()) {return null} // Val queue = PriorityQueue<ListNode>(lists. Size) {node1, node2 -> node1.`val` - node2.`val` } // 1. For (list in lists) {if (null! = list) { queue.offer(list) } } val sentinel = ListNode(-1) var rear = sentinel // 2. While (queue.isnotempty ()) {val node = queue.poll()!! Rear. Next = node rear = node rear = node = node.next) { queue.offer(node.next) } } return sentinel.next } }Copy the code

Complexity analysis:

  • Time complexity: For the binary heap of size K, the time to build the heap is O(k)O(k)O(k) O(k)O(k)O(k) O(k)O(k)O(k) O(k)O(k)O(K āˆ— LGK)O(LGK)O(NK āˆ— LGK)O(NK āˆ— LGK)O(NK āˆ— LGK)O(NK āˆ— LGK)O(NK āˆ— LGK)
  • Space complexity: Binary heap space O(k)O(k)O(k)

5. Sort linked lists

Insertion Sort List Insertion Sort ListĀ |”Antithesis”
A: We have a Sort ListĀ “Antithesis”

6. Circular lists

Linked list intersection-loop problem can be classified as one kind of problem, which appears frequently in interview. In a previous article, we discussed separately: the algorithm of interview questions | chain table fellowship & cyclization problem”

Recommended reading

  • Cryptography | is Base64 encryption algorithm?
  • Java | show you understand the ServiceLoader principle and design idea
  • Use annotations Java | this is a comprehensive strategy (including the Kotlin)
  • Java | reflection: access type information at run time (including the Kotlin)
  • Android | interview will ask Handler, are you sure you don’t look at it?
  • Android | show you understand NativeAllocationRegistry principle and design idea
  • Computer composition principle | Unicode utf-8 and what is the relationship?
  • | why floating-point arithmetic of computer constitute principle is not accurate? (Ali written test)

Thank you! Your “like” is the biggest encouragement for me! Welcome to attentionPeng XuruiThe lot!