linkedList.js

class ListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

let getSum = head => {
  let ans = 0;
  while(head) {
    ans+= head.val
    head = head.next;
  }
}
let addNode = (prevNode, nodeToAdd) => {
  nodeToAdd.next = prevNode.next
  prevNode.next = nodeToAdd
}

let deleteNode = prevNode => {
  prevNode.next = prevNode.next.next
}

class DblListNode {
  constructor(val) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

let dlAddNode = (node, nodeToAdd) => {
  let prevNode = node.prev;
  nodeToAdd.next = node;
  nodeToAdd.prev = prevNode;
  prevNode.next = nodeToAdd;
  node.prev = nodeToAdd;
}

let dlDeleteNode = node => {
  let prevNode = node.prev;
  let nextNode = node.next;
  prevNode.next = nextNode
  nextNode.prev = prevNode;
}

let addToEnd = nodeToAdd => {
  nodeToAdd.next = tail;
  nodeToAdd.prev = tail.prev;
  tail.prev.next = nodeToAdd;
  tail.prev = nodeToAdd;
}

let removeFromEnd = () => {
  if (head.mext == tail) {
    return;
  }
  let nodeToRemove = tail.prev;
  nodeToRemove.prev.next = tail;
  tail.prev = nodeToRemove.prev;
}

let addToStart = nodeToAdd => {
  nodeToAdd.prev = head;
  nodeToAdd.next = head.next;
  head.next.prev = nodeToAdd;
  head.next = nodeToAdd;
}

let removeFromStart = () => {
  if (head.next == tail) {
    return;
  }
  let nodeToRemove = head.next;
  nodeToRemove.next.prev = head;
  head.next = nodeToRemove.next;
}
/*
- Odd number of nodes HEAD, return the value of
the node in the middle

i/p: 1 -> 2 -> 3 -> 4 -> 5
o/p: 3

- load 2 ptrs at the head
- in a while loop with conditon fast & fast.next
- when fast ptr reaches end
- node where slow ptr is at return the val
Time Complexity: O(N)
Space Complexity: O(1)
*/

let getMiddle = head => {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow.val;
}

/*
Given the head of linked list, determine if the
linked list has a cycle

- load 2 ptrs at the head
- in a while with condition fast & fast.next
- scrub fast & slow ptrs
- have a if condition & check fast.val === slow.val
- then return true
- at end of while loop return false

Time Complexity: O(N)
Space Complexity: O(1)
*/
var hasCycle = function(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast === slow) {
      return true
    }
  }
  return false
}

/*
Given the head of a linked list and an integer k, return the kth node from the end.

- give a head start to fast ptr until k using a loop
- in a while with condition fast
- scrub fast & slow ptrs
- at end of while loop return slow value

Time Complexity: O(N)
Space Complexity: O(1)
*/

let findNode = (head, k) => {
  let slow = head;
  let fast = head;

  for (let i = 0;  i <= k; i++) {
    fast = fast.next;
  }
  while (fast) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow
}

/*
Given the head of a singly linked list, return the middle node of the linked list.

- initalize slow & fast ptr
- loop thru ll & find the length
- in a while with condition fast
- scrub fast & slow ptrs
- if odd return slow val
- if else return slow.next val
- 

*/

const middleNode = function(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
};


/*
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

i/p: head = [1,1,2,3,3]
o/p: [1,2,3]

i/p: head = [1,1,2]
o/p: [1,2]
- initalize 2 ptrs,
- in a while loop, with p2 & p2.next 
- compare p1 & p2 values if same
- then delete the node p1.next = p2.next.next
- return 

*/

const deleteDuplicates = (head) {
  let p1 = head;
  let p2 = head.next;

  while (p2 && p2.next) {
    if(p1.val === p2.val) {
      p1.next = p2.next.next;
    }
    p1 = p1.next;
    p2 = p1.next
  }
  return head
};

const reverseList = head => {
  let prev = null;
  let curr = head;
  while (curr) {
    let nextNode = curr.next;
    cur.next = prev;
    prev = curr;
    curr = nextNode;
  }
  return prev;
}


const swapPairs = function(head) {
  // check edge case: linked list has 0 or 1 nodes 
  // just return
  if (!head || !head.next) {
    return head;
  }

  let dummy = head.next; // step 5
  let prev = null; // initalize for step 3
  while (head && head.next) {
    if (prev) {
      prev.next = head.next; // step 4
    }
    prev = head; // step 3
    let nextNode = head.next.next; // step 2
    head.next.next = head; // step 1

    head.next = nextNode; // step 6
    head = nextNode; // move to next pair (step 3)
  }
  return dummy;
}