This article summarizes some high frequency questions about linked lists in Leetcode for further understanding and learning.

concept

A linked list is a non-sequential storage structure on a physical storage unit. The logical order of data elements is realized by linking the order of Pointers in the linked list.

The title

Difficulty: Easy

206. Reverse linked lists

Sword finger Offer 24. Reverse the linked list

Code display:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let p1 = head;
    let p2 = null;
    while (p1) {
        const next = p1.next;
        p1.next = p2;
        p2 = p1;
        p1 = next;
    }
    return p2;
}
Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

21. Merge two ordered lists

25. Merge two sorted lists

Code display:

/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ var mergeTwoLists = function(l1, l2) { const l3 = new ListNode(0); let p1 = l1; let p2 = l2; let p3 = l3; while (p1 || p2) { if (! p1) { p3.next = p2; break; } if (! p2) { p3.next = p1; break; } const r = p1.val > p2.val; if (r) { p3.next = new ListNode(p2.val); p2 = p2.next; } else { p3.next = new ListNode(p1.val); p1 = p1.next; } } p3 = p3.next; return l3.next; }Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

22. The k last node in the linked list

Interview question 02.02. Return the last KTH node

Code display:

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let p1 = head;
    let p2 = head;
    while (k > 0) {
        p2 = p2.next;
        k--;
    }
    while (p1 && p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}
Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

141. Circular linked lists

Code display:

var hasCycle = function(head) {
    let p1 = head;
    let p2 = head;
    while (p1 && p2 && p2.next) {
        p1 = p1.next;
        p2 = p2.next.next;
        if (p1 === p2) return true;
    }
    return false;
}
Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

83. Delete duplicate elements from sorted linked lists

Code display:

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
  let p = head;
  while (p && p.next) {
    if (p.val === p.next.val) {
      p.next = p.next.next;
    } else {
      p = p.next;
    }
  }
  return head;
};
Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

234. Palindrome linked list

Code display:

/** * @param {ListNode} head * @return {boolean} */ var isPalindrome = function(head) { const vals = []; let p1 = head; while (p1) { vals.push(p1.val); p1 = p1.next; } console.log(vals); for (let i = 0, j = vals.length - 1; i < vals.length, j >= 0; i++, j--) { if (vals[i] ! == vals[j]) { return false; } } return true; }Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(n)

Print the linked list from end to end

Code display:

/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function(head) {
    let p1 = head;
    const res = [];
    while (p1) { 
        res.push(p1.val);
        p1 = p1.next;
    }
    return res.reverse();
}
Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(n)

160. Intersecting linked lists

Code display:

/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { if (! headA || ! headB) return false; let p1 = headA; let p2 = headB; while (p1 ! == p2) { p1 = p1 ? p1.next : headB; p2 = p2 ? p2.next : headA; } return p1; };Copy the code

Complexity analysis:

  • Time complexity: O(m+n) : m is the number of linked list nodes A, and n is the number of linked list nodes B.
  • Space complexity: O(1)

Interview question 02.03. Delete the intermediate node

Sword refers to Offer 52. The first common node of two linked lists

Code display:

/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let p1 = headA; let p2 = headB; while (p1 ! = p2) { p1 = p1 ? p1.next : headB; p2 = p2 ? p2.next : headA; } return p1; }Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(n)

203. Remove linked list elements

Code display:

* @param {ListNode} head * @param {number} val * @return {ListNode} */ var removeElements = function(head, val) { if (! head) return null; while (head.val === val) { head = head.next; if (! head) return head; } let p1 = head; let p2 = p1.next; while (p2) { if (p2.val === val) { p1.next = p2.next; p2 = p1.next; } else { p1 = p1.next; p2 = p2.next; } } return head; };Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

18. Remove nodes from the list

Code display:

/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var deleteNode = function(head, val) {
    if (head.val === val) return head.next;
    let p1 = head;
    let p2 = p1.next;
    while (p2) {
        if (p2.val === val) {
            p1.next = p2.next;
        }
        p1 = p1.next;
        p2 = p2.next;
    }
    return head;
}
Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

237. Delete a node from a linked list

Code display:

/**
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
  node.val = node.next.val;
  node.next = node.next.next; 
};
Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

Difficulty: Medium

2. Add two numbers

Code display:

/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  const l3 = new ListNode(0);
  let p1 = l1;
  let p2 = l2;
  let p3 = l3;
  let addOne = 0;
  while(p1 || p2) {
    let v1 = p1 ? p1.val : 0;
    let v2 = p2 ? p2.val : 0;
    const sum = v1 + v2 + addOne;
    addOne = ~~(sum / 10);
    p3.next = new ListNode(sum % 10);
    if (p1) p1 = p1.next;
    if (p2) p2 = p2.next;
    p3 = p3.next;
  }
  if (addOne) p3.next = new ListNode(addOne);
  return l3.next;
}
Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

92. Reverse linked list II

Code display:

/** * @param {ListNode} head * @param {number} left * @param {number} right * @return {ListNode} */ var reverseBetween =  function(head, left, right) { let p1 = new ListNode(-1); p1.next = head; let p2 = p1; for (let i = 0; i < left - 1; i++) { p2 = p2.next; } let cur = p2.next; for (let i = 0; i < right - left; i++) { const next = cur.next; cur.next = next.next; next.next = p2.next; p2.next = next; } return p1.next; }Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

143. Rearrange linked lists

Code display:

/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {void} Do not return anything, modify head in-place instead. */ var reorderList = function(head) { if (! head) return head; const temp = []; while (head) { temp.push(head); head = head.next; } let i = 0; j = temp.length - 1; while (i < j) { temp[i].next = temp[j]; i++; if (i === j) break; temp[j].next = temp[i]; j--; } temp[i].next = null; return temp[0]; };Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

Delete duplicate element II from sorted list

Code display:

/** * @param {ListNode} head * @return {ListNode} */ var deleteDuplicates = function(head) { if (! head) return head; const l1 = new ListNode(0, head); let p1 = l1; while (p1.next && p1.next.next) { if (p1.next.val === p1.next.next.val) { const v = p1.next.val; while (p1.next && p1.next.val === v) { p1.next = p1.next.next; } } else { p1 = p1.next; } } return l1.next; }Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

Delete the NTH node from the list

Code display:

/** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { if (! head) return head; const l1 = new ListNode(0, head); let p1 = l1; let p2 = p1; while (p2) { p2 = p2.next; n--; } while (p1 && p2) { if (! p2.next) { p1.next = p1.next ? p1.next.next : null; } p1 = p1.next; p2 = p2.next; } return l1.next; };Copy the code

Complexity analysis:

  • Time complexity: O(n) : n indicates the number of nodes in the linked list.
  • Space complexity: O(1)

148. Sort linked lists

Ideas:

  • Merge sort is used to split the list in half until it reaches a single list node

  • Then the merge method is used to sort and merge each independent linked list, and finally output a sorted linked list

The code shown

/** * @param {ListNode} head * @return {ListNode} */ var sortList = function (head) { if (! head || ! head.next) return head; let slow = head, fast = head; let preSlow = null; while (fast && fast.next) { preSlow = slow; // preSlow saves the first half of the list slow = slow.next; // Slow is half as fast as fast fast = fast.next. } preslow. next = null; Const l = sortList(head); // preslow.next = null; Const r = sortList(slow); // merge(l, r); // Merge (l, r); } var merge = function (l1, l2) {const dummy = new ListNode(-1); let p0 = dummy; let p1 = l1; let p2 = l2; while (p1 && p2) { if (p1.val < p2.val) { p0.next = p1; p1 = p1.next; } else { p0.next = p2; p2 = p2.next; } p0 = p0.next; } if (p1) p0.next = p1; if (p2) p0.next = p2; return dummy.next; }Copy the code

Complexity analysis:

  • Time complexity: O(nlogn)

  • Space complexity: O(logn)

Interview question 02.05. Linked list summation

86. Separate linked lists

61. Rotate linked lists

142. Circular linked List II

445. Add two numbers II

Insert sort on linked lists

328. Odd-even linked lists

138. Copy linked lists with random Pointers

Swap nodes in a linked list in pairs

Difficulty: difficulty

25. Flip linked lists in groups of K

Merge K ascending linked lists

Conclusion:

The linked list data structure is a bit difficult for me to operate and requires a lot of practice and understanding.