Algorithm - LeetCode Problems 21

Problem 876. Middle of the Linked List

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

• If there are two middle nodes, return the second middle node.

Examples

• Example 1:
  • Input: head = [1,2,3,4,5]
  • Output: [3,4,5]
  • Explanation: The middle node of the list is node 3.

• Example 2:
  • Input: head = [1,2,3,4,5,6]
  • Output: [4,5,6]
  • Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints

• The number of nodes in the list is in the range [1, 100].
• 1 <= Node.val <= 100

Solution

/**
 * 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 {ListNode}
 */
var middleNode = function(head) {
    let node = head;
    let answer = head;
    let nodeCount = 0;

    while (node) {
        node = node.next;
        nodeCount++;
    }

    let middleIndex = Math.floor(nodeCount / 2);

    while (middleIndex) {
        answer = answer.next;
        middleIndex--;
    }

    return answer;
};

Problem 19. Remove Nth Node From End of List

• Given the head of a linked list, remove the nth node from the end of the list and return its head.

Examples

• Example 1:

  • Input: head = [1,2,3,4,5], n = 2
  • Output: [1,2,3,5]

• Example 2:

  • Input: head = [1], n = 1
  • Output: []

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let node = head;
    let nodeCount = 0;

    while (node) {
        node = node.next;
        nodeCount++;
    }

    if (nodeCount === n) {
        head = head.next;
        return head;
    }

    let removedNodeIndex = nodeCount - n - 1;
    node = head;
    nodeCount = 0;

    while (node) {
        if (nodeCount === removedNodeIndex) {
            node.next = node.next.next;
        }
        node = node.next;
        nodeCount++;
    }

    return head;
};

Problem 24. Swap Nodes in Pairs

• Given a linked list head, swap every two adjacent nodes and return its head.
  • You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Examples

• Example 1:

  • Input: head = [1,2,3,4]
  • Output: [2,1,4,3]

• Example 2:

  • Input: head = []
  • Output: []

• Example 3:

  • Input: head = [1]
  • Output: [1]

Constraints

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

Solution

/**
 * 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 {ListNode}
 */
var swapPairs = function(head) {
    let answer = new ListNode(0);
    let node = answer;
    answer.next = head;

    if (!head || !head.next) {
        return head;
    }

    while (node.next && node.next.next) {
        const node1 = node.next;
        const node2 = node.next.next;
        node.next = node2;
        node1.next = node2.next;
        node2.next = node1;
        node = node.next.next;
    }

    return answer.next;
};

Problem 2807. Insert Greatest Common Divisors in Linked List

• Given the head of a linked list head, in which each node contains an integer value.

• Between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor of them.

• Return the linked list after insertion.

• The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

Examples

• Example 1:
  • Input: head = [18,6,10,3]
  • Output: [18,6,6,2,10,1,3]
    Explanation:
    • The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes).
      • We insert the greatest common divisor of 18 and 6 = 6 between the 1st and the 2nd nodes.
      • We insert the greatest common divisor of 6 and 10 = 2 between the 2nd and the 3rd nodes.
      • We insert the greatest common divisor of 10 and 3 = 1 between the 3rd and the 4th nodes.
    • There are no more adjacent nodes, so we return the linked list.

• Example 2:
  • Input: head = [7]
  • Output: [7]
  • Explanation:
    • The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes.
    • There are no pairs of adjacent nodes, so we return the initial linked list.

Constraints:

• The number of nodes in the list is in the range [1, 5000].
• 1 <= Node.val <= 1000

Solution

/**
 * 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 {ListNode}
 */
var insertGreatestCommonDivisors = function(head) {
  const getGreatestCommonDivisors = (num1, num2) => {
      const smallNumber = num1 > num2 ? num1 : num2;
      for (let i = smallNumber; i > 1; i--) {
          if (num1 % i === 0 && num2 % i === 0) {
              return i;
          }
      }
      return 1;
    };
    let node = head;

    while (node && node.next) {
        const node1 = node;
        const node2 = node.next;
        const greatestCommonDivisors = getGreatestCommonDivisors(node1.val, node2.val);
        const divisorNode = new ListNode(greatestCommonDivisors);
        node1.next = divisorNode;
        divisorNode.next = node2;
        node = node2;
    }

    return head;
};