Linked list class topic experience

Because the linked list is not convenient to store and value, some variables should be used to temporarily store key nodes before operation of the linked list. When solving the problem, it is necessary to determine the key nodes after clarifying the idea of the topic, and then carry out related operations of the linked list to avoid losing the reference of key nodes

For the special case processing of the header, a temporary header can be established to facilitate the unified processing of subsequent nodes

Inverts the linked list from position m to n

Input: 1 - > 2 - > 3 - > 4 - > 5 - > NULL, m = 2, n = 4 output: 1 - > > 4-3 - > 2 - > 5 - > NULLCopy the code
/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/** * key nodes: * 1. M after the previous node is flipped, its next should point to the node at the original n position * 2. M after the next node is flipped, its next should point to the node at the original N position * 3. n node * 4.n node */
/** * @param {ListNode} head * @param {number} m * @param {number} n * @return {ListNode} * 1 ≤ m ≤ n ≤ The length of the list. * /
var reverseBetween = function(head, m, n) {
  let change_len = n - m + 1  // Number of nodes to be reversed
  let pre_head = null // It is used to determine whether to start the inversion from the first node
  let result = head
  
  while (head && --m) {
    pre_head = head
    head = head.next
  }
  let rev_head = head  // Cache the node at position m

  // reverse the nodes between m->n
  let pre = null
  while (head && change_len) {
    let next = head.next
    head.next = pre
    pre = head
    head = next
    change_len--
  }
  // m->n after the inversion is complete, pre points to the node at the original n position (now at the m position) and head points to the next node at the original N position
  // rev_head is now in the original n position
  rev_head.next = head
  if (pre_head) {
    pre_head.next = pre // Do not reverse from the first
  } else {
    result = pre
  }
  return result
};
Copy the code

Removes duplicate elements from sorted linked lists

Input: 1->1->2->3->3 Output: 1->2->3Copy the code
/** * @param {ListNode} head * @return {ListNode} */
var deleteDuplicates = function(head) {
  let cur = head
  while (cur && cur.next) {
    if (cur.val === cur.next.val) {
      cur.next = cur.next.next
    } else {
      cur = cur.next
    }
  }
  return head
};
Copy the code

Given a linked list and a particular value x, separate the list so that all nodes less than x precede those greater than or equal to x. You should preserve the initial relative position of each node in the two partitions.

Input: the head = 1 - > > 4-3 - > 2 - > - > 2, 5 x = 3 output: 1 - > 2 - > 4 - > 2 - > 3 - > 5Copy the code
/** * create a list of large elements and a list of small elements, then concatenate * key nodes: the first and last elements of the large list and the first and last elements of the small list */
/** * @param {ListNode} head * @param {number} x * @return {ListNode} */
var partition = function(head, x) {
  let max_head = new ListNode(0)
  let min_head = new ListNode(0)
  let max_prt = max_head
  let min_prt = min_head
  while (head) {
    let val = head.val
    if (val >= x) {
      max_prt.next = head
      max_prt = head
    } else {
      min_prt.next = head
      min_prt = head
    }
    head = head.next
  }
  min_prt.next = max_head.next
  max_prt.next = null
  return min_head.next
};
Copy the code

Circular list Given a linked list, returns the first node where the list begins to loop. Returns NULL if the list is loopless.

/** * @param {ListNode} head * @return {ListNode} */
var detectCycle = function(head) {
  if(! head || ! head.next) {return null
  }
  // Step 1: use the fast or slow pointer to check whether the list has a ring
  let fast = head
  let slow = head
  let hasCycle = false
  while (fast.next && fast.next.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) {
      hasCycle = true
      break}}// Step 2: If there is a loop, find the node where the loop begins
  if (hasCycle) {
    let start = head
    while(start ! == slow) { start = start.next slow = slow.next }return start
  } else {
    return null}};Copy the code

Intersecting lists Finds the starting node where two single-linked lists intersect.

/** * If two lists intersect, the length after the point of intersection is the same. * Let two lists traverse from the same distance at the end of the same distance. This position can only be the head of a shorter list. * To do this, we must eliminate the length difference between the two lists * 1. PA points to A and pB points to B, iterating backwards * 2. If pA reaches the end, pA = headB continues traversal * 3. If pB reaches the end, then pB = headA continues traversing * 4. When a longer list pointer points to a shorter list head, the length difference is eliminated
/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */
var getIntersectionNode = function(headA, headB) {
  let a = headA
  let b = headB
  if(a === null || b === null) return null
  // do not intersect with null===null
  while(a ! = b) { a = a ===null ? headB : a.next
    b = b === null ? headA : b.next
  }
  return a
};
Copy the code

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

Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4Copy the code
/** * create a temporary list, compare two lists, and concatenate them with a temporary list */
/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */
var mergeTwoLists = function(l1, l2) {
  let tempHead = new ListNode(0)
  let cur = tempHead
  while (l1 && l2) {
    if (l1.val < l2.val) {
      cur.next = l1
      cur = cur.next
      l1 = l1.next
    } else {
      cur.next = l2
      cur = cur.next
      l2 = l2.next
    }
  }
  // If either one is empty, join the other list directly
  if(! l1) { cur.next = l2 }if(! l2) { cur.next = l1 }return tempHead.next
};
Copy the code
/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */
// A recursive solution
var mergeTwoLists = function(l1, l2) {
    if(l1 === null) return l2
    if(l2 === null) 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