LinkedList

Question 1

Write a function to delete a node in a singly-linked list. You will not be given access to the head of the list, instead you will be given access to the node to be deleted directly.

It is guaranteed that the node to be deleted is not a tail node in the list.

Answer 1

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @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;
};

Question 2

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Answer 2

/**
 * 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 reverseList = function(head) {
    let prev = null;
    let cur = head;
    let next = null;

    while (cur) {
        next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
};

Question 3

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

Answer 3

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    const mergedList = {};
    let mergedCurNode = mergedList;

if (!l1) {
    return l2;
}

if (!l2) {
    return l1;
}

    while (l1 && l2) {
        if (l1.val <= l2.val) {
            mergedCurNode.next = l1;
            l1 = l1.next
        } else {
            mergedCurNode.next = l2;
            l2 = l2.next;
        }
        mergedCurNode = mergedCurNode.next;
    }

if (l1) {
    mergedCurNode.next = l1;
}

if (l2) {
    mergedCurNode.next = l2;
}

return mergedList.next; };

Question 4

Given head, the head of a linked list, determine if the linked list has a cycle in it.

Answer 4

/**

• Definition for singly-linked list.
• function ListNode(val) {
• this.val = val;
• this.next = null;
• }
• /

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let oneStep = head;
    let twoStep = head;
    while (oneStep && twoStep && twoStep.next) {
        oneStep = oneStep.next;
        twoStep = twoStep.next.next;
        if (oneStep === twoStep) {
            return true;
        }
    }
    return false;
};

Question 5

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Answer 5

/**
 * 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} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    const beforeHead = {};
    let before = beforeHead;
    const afterHead = {};
    let after = afterHead;

    while (head) {
        if (head.val < x) {
            before.next = head;
            before = before.next;
        } else {
            after.next = head;
            after = after.next;
        }
        head = head.next;
    }

after.next = null;
before.next = afterHead.next;
return beforeHead.next; };

Question 6

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

Answer 6

/**
 * 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 oddEvenList = function(head) {
    const oddHead = {};
    let odd = oddHead;
    const evenHead = {};
    let even = evenHead;
    let counter = 0;
    while (head) {
        counter++
        if (counter % 2 === 0) {
            even.next = head;
            even = even.next;
        } else {
            odd.next = head;
            odd = odd.next;
        }
        head = head.next;
    }

even.next = null;
odd.next = evenHead.next;
return oddHead.next; };

Question 7

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

Answer 7

/**
 * 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) {
    const dummy = {};
    dummy.next = head;
    let length = 0;
    let curNode = head;

while (curNode) {
    length++;
    curNode = curNode.next;
}

length -= n;

curNode = dummy;

    while (length > 0) {
        length--;
        curNode = curNode.next;
    }
    curNode.next = curNode.next.next;
    return dummy.next;
};

Question 8

Write a program to find the node at which the intersection of two singly linked lists begins.

Answer 8

/**

• Definition for singly-linked list.
• function ListNode(val) {
• this.val = val;
• this.next = null;
• }
• /

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(head1, head2) {
    let p1 = head1;
    let p2 = head2;
    let len1 = 0;
    let len2 = 0;

while (p1) {
    len1 += 1;
    p1 = p1.next;
}

while (p2) {
    len2 += 1;
    p2 = p2.next;
}

p1 = head1;
p2 = head2;

    if (len1 > len2) {
        const diff = len1 - len2;

        for (let i = 0; i < diff; i++) {
            p1 = p1.next;
        }
    } else {
        const diff = len2 - len1;

        for (let i = 0; i < diff; i++) {
            p2 = p2.next;
        }
    }

while (p1 !== p2) {
    p1 = p1.next;
    p2 = p2.next;
}

return p1; };

Question 9

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Answer 9

/**

• // Definition for a Node.
• function Node(val, next, random) {
• this.val = val;
• this.next = next;
• this.random = random;
• };
• /

/**
 * @param {Node} head
 * @return {Node}
 */
var copyRandomList = function(start) {
    let curr = start, temp = null;  

    // insert additional node after  
    // every node of original list  
    while (curr != null)  
    {  
        temp = curr.next;  

        // Inserting node  
        curr.next = { val: curr.val, next: null };  
        curr.next.next = temp;  
        curr = temp;  
    }
    curr = start;  

// adjust the random pointers of the  
// newly added nodes  
while (curr != null)  
{  
    if(curr.next != null)  
        curr.next.random = (curr.random != null) 
                  ? curr.random.next : curr.random;  

    // move to the next newly added node by  
    // skipping an original node  
    curr = (curr.next != null) ? curr.next.next  
                                    : curr.next;  
}

let original = start;

    if (original == null) {
        return original;
    }

let copy = start.next;

    // save the start of copied linked list  
    temp = copy;  

// now separate the original list and copied list  
while (original != null && copy != null)  
{  
    original.next = (original.next != null)?  
                original.next.next : original.next;  

    copy.next = (copy.next != null) ? copy.next.next  
                                        : copy.next;  
    original = original.next;  
    copy = copy.next;  
}  
return temp;  };

Question 10

Given a singly linked list, determine if it is a palindrome.

Answer 10

/**
 * 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 {boolean}
 */
var isPalindrome = function(head) {
    if(head == null || head.next == null)
        return true;
    // find list center
    let fast = head;
    let slow = head;

while(fast.next!=null && fast.next.next!=null){
    fast = fast.next.next;
    slow = slow.next;
}

    let secondHead = slow.next;
    slow.next = null;

    //reverse second part of the list
    let p1 = secondHead;
    let p2 = p1.next;

    while(p1!=null && p2!=null){
        let temp = p2.next;
        p2.next = p1;
        p1 = p2;
        p2 = temp;
    }

secondHead.next = null;

    //compare two sublists now
    let p = (p2==null?p1:p2);
    let q = head;
    while(p!=null){
        if(p.val != q.val)
            return false;

    p = p.next;
    q = q.next;

}

return true; };

Question 11

Given the head of a linked list, return the list after sorting it in ascending order.

Answer 11

/**
 * 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 sortList = function(head) {
    if (head == null || head.next == null)
            return head;
        let mid = getMid(head);
        let left = sortList(head);
        let right = sortList(mid);
        return merge(left, right);
};

    var merge = function(list1, list2) {
        const dummyHead = {};
        let tail = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
                tail = tail.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
                tail = tail.next;
            }
        }
        tail.next = (list1 != null) ? list1 : list2;
        return dummyHead.next;
    }

    var getMid = function(head) {
        let midPrev = null;
        while (head != null && head.next != null) {
            midPrev = (midPrev == null) ? head : midPrev.next;
            head = head.next.next;
        }
        let mid = midPrev.next;
        midPrev.next = null;
        return mid;
    }