Fix algorithms – Linked list topics

The list

Those of you who know a linked list know that it’s a series of Pointers that connect a bunch of discrete pieces of memory. The content requirements of visible lists are reduced, but the performance of random access is simply not as good, requiring O(n) time complexity.

How do I operate linked lists

The operation of and linked list is mainly to add and delete, in fact, the operation of linked list is also the operation of Pointers between linked lists. Its data structure is roughly as follows:

Var node = {val: 1, next: {// next: {var node = {val: 1, next: {// next: {Copy the code

The operation on the linked list is simply to change the pointer to it, by changing the value of next to the corresponding node.

Leedcode bo

Without further ado, let’s do a few linked list questions, which are often tested in the interview.

Merge two ordered lists (leedcode21)

Leetcode-cn.com/problems/me…

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.

Idea 1 (Recursion)

  • Merge the smaller of the two list heads with the remaining elements
  • The recursion terminates when one of the two lists is empty

Complexity analysis

N plus M is the length of the two lists

  • Time complexity :(M+N)
  • Spatial complexity :(M+N)
 const mergeTwoLists  = function  (l1, l2) {
    if(! l1) {return l2
    }
    if(! l2) {return l1
    }
    if(l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next,l2)
        return l1
    }else {
        l2.next = mergeTwoLists(l2.next,l1)
        return l2
    }
 }
Copy the code

Idea 2 (Iteration)

  • Define a ‘sub-node’prev
  • Add the smaller head of the two lists to the next node of the ‘sub-node’
  • Move the node in the corresponding linked list one bit back.

Complexity analysis

N plus M is the length of the two lists

  • Time complexity :(M+N)
  • Space complexity: 1 (we only need constant space for several variables.)
var mergeTwoLists = function(l1, l2) {
   var preNode = new ListNode(-1),
   prev = preNode
   while(l1&&l2){
       if(l1.val <l2.val) {
           prev.next = l1
           l1 = l1.next
       }else {
           prev.next = l2
           l2 = l2.next
       }
       prev = prev.next
   }
    l1 === null ? prev.next = l2 :prev.next = l1
    return preNode.next
};
Copy the code

Reverse linked list (leedcode206)

Leetcode-cn.com/problems/re…

Idea 1 (Recursion)

  • Of the current nodenextIs null, the recursion ends, and the last node is found
  • Let the last node point to the previous node
  • The previous node pointed to empty (if this is ignored, you can have rings in the linked list)

Complexity analysis

  • Time complexity: O(n), where n is the length of the list. You need to reverse each node of the linked list.

  • Spatial complexity: O(n), where n is the length of the linked list. The spatial complexity depends primarily on the stack space of recursive calls, which is at most N layers.

var reverseList = function(head) {
    if(head === null || head.next === null) return head
   	var node = reverseList(head.next)
    head.next.next = head
    head.next = null
    return node
};
Copy the code

Idea 2 (Iteration)

  • Initialize the precursor node to NULL and the target node to the head node
  • Walk through the linked list and record the next nodes
  • The prev and CURr Pointers move forward one step each
  • After the inversion, the prev becomes the new head node

Complexity analysis

  • Time complexity: O(n), where n is the length of the list. You need to reverse each node of the linked list.

  • Space complexity: O(1)

var reverseList = function(head) {
    let prev = null
    let curr = head
    while(curr ! =null) {
        var next = curr.next
        curr.next = prev 
        prev = curr
        curr = next 
    }
    return prev
};
Copy the code

Circular linked list (leedcode141)

Leetcode-cn.com/problems/li…

Idea 1 (double pointer method)

  • The fast pointer moves two steps at a time and the full pointer moves one step at a time
  • If there is no loop, the fast pointer reaches the tail first, returning false

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(1)
var hasCycle = function(head) {
 if(! head || ! head.next)return fasle
 let fast = head.next
 let slow =  head
 while(fast ! = slow){if(! fast || ! fast.next)return false
	fast = fast.next.next
 	slow = slow.next
 }
 return ture
};
Copy the code

Idea 2 (Hash)

  • Traverses the node to determine whether the hash table has the current node
  • If no current node is added to the hash, if there is a ring

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(1)
var hasCycle = function(head) {
 var map = new Map(a)while(head) {
     if(map.has(head)) {
         return true
     }else{
         map.set(head,true)
         head = head.next
     }
 }
 return false
};
Copy the code

Delete the penultimate node of a node (leedCode19)

Leetcode-cn.com/problems/re…

Idea 1 (Violent solution)

  • The NTH node is the same thing as taking the frontTotal length of the list – NTH node + 1A node
  • I’m going to find the n-1 node which is the last nodeTotal length of the list – number NTH nodeI’m going to point to the next node

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(1)
var removeNthFromEnd = function(head, n) {
    var l = getLinkLength(head) // Get the total length of the list
    var dummy = new ListNode(0, head);
    var cur = dummy;
    for (var i = 1; i < l - n + 1; i++) {
            cur = cur.next;
    }
        cur.next = cur.next.next;
        return dummy.next;
};
 function getLinkLength(head) {
     var index = 0
     while(head) {
         index++
         head = head.next
     }
     return index
 }
Copy the code

Idea 2 (double pointer method)

  • To delete the NTH node, we need to find the NTH -1 node, and point to the NTH +1 node
  • Add pre, which you can call a sentinel node, to handle boundary issues
  • Use two Pointers, fast PointersfirstFirst n steps are taken, and then the fast and slow Pointers move forward synchronously until first and second are null
  • Returns the prev. Next

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(1)
var removeNthFromEnd = function(head, n) {
    var prev = new ListNode(0,head)
    var first = head
    var second = prev
    for (var i = 0; i<n; i++) { first = first.next }while(first) {
        first = first.next
        second = second.next
    }
    second.next = second.next.next
    return prev.next
};
Copy the code

Find intermediate node of linked list (leedcode876)

Leetcode-cn.com/problems/mi…

Thinking (fast and slow pointer method)

  • Use a fast or slow pointer, where the fast pointer takes two steps at a time and the slow pointer takes one.
  • When the pointer reaches the end, the slow pointer just goes to the middle

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(1)
var middleNode = function(head) {
    let fast = head
    let slow = head
    while(fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
    }
    return slow
};
Copy the code

Palindrome linked list (advanced) (leedcode234)

Use intermediate nodes of linked lists and reverse linked lists

Leetcode-cn.com/problems/pa…

Idea (Using intermediate nodes and reverse lists)

  • Find the intermediate node of the linked list, reverse the head node is the linked list of intermediate nodes
  • Iterate over whether two linked list nodes are the same

Complexity analysis

  • Time complexity: O(n)
  • Space complexity: O(1)
var isPalindrome = function(head) {
    let fast = head;
    /** median */
    let mid = head;
    while (fast && fast.next) {
        mid = mid.next;
        fast = fast.next.next;
    }

    let newH = reverseList(mid);
    while (newH && head) {
        if(newH.val ! = head.val) {return false;
        }
        newH = newH.next;
        head = head.next;
    }
    return true;
};

/** reverse linked list */
var reverseList = function(head) {
    if(! head || ! head.next)return head;
    let end = head;
    while (end.next) {
        let newH = end.next;
        end.next = end.next.next;
        newH.next = head;
        head = newH;
    }
    return head;
};
Copy the code

Switch nodes in a linked list in pairs (LeedCode24)

Leetcode-cn.com/problems/sw…

Thinking (iteration)

  • Define a sentry node, dummyHead, and initialize the arrived node temp. Each loop defines a pointer to node1 and node2
  • Node2 points to node1, which points to the next node on Node2
  • Temp = node1;

The complexity of the

Time complexity: O(n), where n is the number of nodes in the linked list. You need to update Pointers on each node.

Space complexity: O(1).

const dummyHead = new ListNode(0);
    dummyHead.next = head;
    let temp = dummyHead;
    while(temp.next ! = =null&& temp.next.next ! = =null) {
        const node1 = temp.next;
        const node2 = temp.next.next;
        temp.next = node2;
        node1.next = node2.next;
        node2.next = node1;
        temp = node1;
    }
    return dummyHead.next;
Copy the code

92. Reverse linked list II (leedcode92)

Unlike problem 206, given the left and right nodes, reverse the node between the two nodes

【 double pointer 】

var reverseBetween = function(head, left, right) {
    let newHead = new ListNode(-1)
    newHead.next = head
    let cur = newHead,before,after  // before saves the left node, after is the after node
    for(let i = 1; i< left; i++) { cur = cur.next } before = cur cur = cur.next before.next =null
    var prev = null
    for(letj = left ; j<=right; j++) {if(cur == null)    break;
        if(j == right) {after = cur.next}  
        var temp = cur.next  // Normal reversal
        cur.next = prev
        prev = cur
        cur = temp
    }
        before.next = prev
    
    while(prev.next) {
        prev = prev.next  
    }
    
    prev.next = after
    return newHead.next
};
Copy the code

Leetcode-cn.com/problems/re…

conclusion

Please pay attention to the following will continue to update