Linked List - Githubissues

hon9g commented 4 years ago

Problems selected by LeetCode for the topic Linked List 🌐

Click ✔️ to go to each solution. The Link to each problem🌐 is at the top of each solution.

🔗 Singly Linked List

#	title	my solution
707	Design Linked List	✔️

🔗 Two Pointer Technique

#	title	my solution
141	Linked List Cycle	✔️
142	Linked List Cycle II	✔️
160	Intersection of Two Linked Lists	✔️
19	Remove Nth Node From End of List	✔️

🔗 Classic Problems

#	title	my solution
206	Reverse Linked List	✔️
203	Remove Linked List Elements	✔️
328	Odd Even Linked List	✔️
234	Palindrome Linked List	✔️

🔗 Doubly Linked List

#	title	my solution
707	Design Linked List	✔️

🔗 Conclusion

#	title	my solution
21	Merge Two Sorted Lists	✔️
2	Add Two Numbers	✔️
430	Flatten a Multilevel Doubly Linked List	✔️
708	Insert into a Cyclic Sorted List	✔️
138	Copy List with Random Pointer	✔️
61	Rotate List	✔️

hon9g commented 4 years ago

707. Design Linked List

🌐problem
Singly Linked List
Time complexity:
- O(1) for addAtHead,
- O(I) for get, addAtIndex, deleteAtIndex,
- O(N) for addAtTail

Space complexity: O(N)


/**
* Linked List
*/
var MyLinkedList = function() {
this.head = new ListNode(-1);
this.size = 0;
};

/**

Get the value of the index-th node in the linked list. If the index is invalid, return -1.
@param {number} index
@return {number} */ MyLinkedList.prototype.get = function(index) { if (index < 0 || this.size <= index) return -1; let curr = this.head.next; while (index--) { curr = curr.next; } return curr.val; };

/**

Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
@param {number} val
@return {void} */ MyLinkedList.prototype.addAtHead = function(val) { this.addAtIndex(0, val); };

/**

Append a node of value val to the last element of the linked list.
@param {number} val
@return {void} */ MyLinkedList.prototype.addAtTail = function(val) { this.addAtIndex(this.size, val); };

/**

Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
@param {number} index
@param {number} val
@return {void} */ MyLinkedList.prototype.addAtIndex = function(index, val) { if (this.size < index) return; if (index < 0) index = 0; this.size++; let prev = this.head; while (index--) { prev = prev.next; } const toAdd = new ListNode(val); toAdd.next = prev.next; prev.next = toAdd; };

/**

Delete the index-th node in the linked list, if the index is valid.
@param {number} index
@return {void} */ MyLinkedList.prototype.deleteAtIndex = function(index) { if (index < 0 || this.size <= index) return; this.size--; let prev = this.head; while (index--) { prev = prev.next; } prev.next = prev.next.next; };
```
### Doubly Linked List
**implementation**
- there are dummy node for head and tail.
- It can get length in constant time.
```

complexity analysis

Time complexity:
- O(1) for addAtHead, addAtTail
- O(I) for get, addAtIndex, deleteAtIndex,
Space complexity: O(N)

/**
 * Node Constructor
 */
const Node = function(val=null, prev=null, next=null) {
    this.val = val;
    this.prev = prev;
    this.next = next;
};

/**
 * Linked List Constructor
 */
const MyLinkedList = function() {
    this.length = 0;
    this.head = new Node();
    this.tail = new Node();
    this.head.next = this.tail;
    this.tail.prev = this.head;
};

/**
 * Get the value of the index-th node in the linked list. If the index is invalid, return -1. 
 * @param {number} i
 * @return {number}
 */
MyLinkedList.prototype.get = function(i) {
    if (i < 0 || i >= this.length) return -1;
    if (i + 1 === this.length) return this.tail.prev.val;
    let curr = this.head.next;
    while (i--) curr = curr.next;
    return curr.val;
};

/**
 * Add a node of value val before the first element of the linked list.
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
    this.length++;
    const nextNode = this.head.next;
    const node = new Node(val, this.head, nextNode);
    this.head.next = node, nextNode.prev = node;
};

/**
 * Append a node of value val to the last element of the linked list. 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
    this.length++;
    const prevNode = this.tail.prev;
    const node = new Node(val, prevNode, this.tail);
    this.tail.prev = node, prevNode.next = node;
};

/**
 * Add a node of value val before the i-th node in the linked list.
 * @param {number} i
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(i, val) {
    if (i < 0 || this.length < i) return;
    if (i === this.length) {
        this.addAtTail(val);
        return;
    }
    this.length++;
    let curr = this.head;
    while (i--) curr = curr.next;
    const nextNode = curr.next;
    const node = new Node(val, curr, nextNode);
    curr.next = node, nextNode.prev = node;
};

/**
 * Delete the i-th node in the linked list, if the index is valid. 
 * @param {number} i
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(i) {
    if (this.length <= i || i < 0) return;
    this.length--;
    if (i === this.length) {
        this.tail.prev = this.tail.prev.prev;
        return;
    }
    let curr = this.head;
    while(i--) curr = curr.next;
    curr.next = curr.next.next;
};

hon9g commented 4 years ago

141. Linked List Cycle

🌐problem
Hash Set
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {ListNode} head
* @return {boolean}
*/
const hasCycle = function(head) {
const hashSet = new Set();
while (head) {
    hashSet.add(head);
    if (hashSet.has(head.next)) {
        return true
    }
    head = head.next;
}
return false;
};

class Solution:
def hasCycle(self, head: ListNode) -> bool:
    hash_set = set()
    while head:
        hash_set.add(head)
        if head.next in hash_set:
            return True
        head = head.next
    return False

Two Pointer

Time complexity: O(N)

Space complexity: O(1)

/**
* @param {ListNode} head
* @return {boolean}
*/
const hasCycle = function(head) {
let turtle = head, rabbit = head ? head.next : null;
while (turtle && rabbit) {
    if (turtle === rabbit) {
        return true;
    }
    turtle = turtle.next;
    rabbit = rabbit.next ? rabbit.next.next : null;
}
return false;
};

class Solution:
def hasCycle(self, head: ListNode) -> bool:
    turtle, rabbit = head, head.next if head else None
    while turtle and rabbit:
        if turtle == rabbit:
            return True
        turtle = turtle.next
        rabbit = rabbit.next.next if rabbit.next else None
    return False

Change values

Time complexity: O(N)

Space complexity: O(1)

/**
* @param {ListNode} head
* @return {boolean}
*/
const hasCycle = function(head) {
while (head) {
    if (head.val === "#") {
        return true;
    }
    head.val = "#";
    head = head.next;
}
return false;
};

hon9g commented 4 years ago

142. Linked List Cycle II

🌐problem
Hash Set
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {ListNode} head
* @return {ListNode}
*/
const detectCycle = function(head) {
const hashSet = new Set();
while (head) {
    hashSet.add(head);
    if (hashSet.has(head.next)) {
        return head.next;
    }
    head = head.next;
}
return null;
};

Floyd's Tortoise and Hare

Time complexity: O(N)

Space complexity: O(1)

/**
* @param {ListNode} head
* @return {ListNode}
*/
const detectCycle = function(head) {
let tortoise = head, hare = head, intersec;
while (tortoise && hare) {
    tortoise = tortoise.next;
    hare = hare.next ? hare.next.next : null;
    if (tortoise == hare) {
        intersec = tortoise;
        break;
    }
}
while (head && intersec) {
    if (head === intersec) {
        return head;
    }
    head = head.next;
    intersec = intersec.next;
}
return null;
};

hon9g commented 4 years ago

160. Intersection of Two Linked Lists

🌐problem
Hash Set

A = number of following nodes from headA B = number of following nodes from headB
Time complexity: O(A+B)

Space complexity: O(A)

Traverse List A and add nodes into the Hash Set.
Traverse List B abd check whether the node is in the Hash Set. If It is in the hash set return that node immediately.

If all of the traverse is done; there are no intersection between two Lists.

/**
* @param {ListNode} headA
* @param {ListNode} headB
* @return {ListNode}
*/
const getIntersectionNode = (headA, headB) => {
const seen = new Set();
while (headA) {
seen.add(headA);
headA = headA.next;
}
while (headB) {
if (seen.has(headB)) {
    return headB;
}
headB = headB.next;
}
return null;
};

Floyd's Tortoise and Hare algorithm

Time complexity: O(A+B)
Space complexity: O(1)
1. Make the last node in list A points to the first node in list B. If the two linked lists have intersections, a linked list A+B has a cycle.

For each iteration, move the tortoise pointer once and move the hare pointer twice to find the intersection. If there is no cycle, the hare pointer will be null and exit the loop.
If there are intersected nodes in the A+B list, move the head and intersected node with same speed in A+B list to find the node where the cycle begins. (If there are no nodes intersected, this step will not run.)

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
const getIntersectionNode = (headA, headB) => {
    let tortoise = headA, hare = headA, curr = headA;
    while (curr) {
        if (!curr.next) {
            curr.next = headB;
            break;
        }
        curr = curr.next;
    }
    while (tortoise && hare) {
        tortoise = tortoise.next;
        hare = hare.next ? hare.next.next : null;
        if (tortoise === hare) {
            break;
        }
    }
    while (headA && hare) {
        if (headA === hare) {
            break;
        }
        headA = headA.next;
        hare = hare.next;
    }
    if (curr) curr.next = null;
    return hare;
};

Different Counts of Nodes

Time complexity: O(A+B)

Space complexity: O(1)


/**
* @param {ListNode} head
* @return {number}
*/
const countNodes = head => {
let n = 0;
while (head) {
    head = head.next;
    n++;
}
return n;
}

/**

@param {ListNode} headA
@param {ListNode} headB
@return {ListNode} */ const getIntersectionNode = (headA, headB) => { let a = countNodes(headA), b = countNodes(headB); while (a > b) { if (!headA) return null; headA = headA.next a--; } while (b > a) { if (!headB) return null; headB = headB.next; b--; } while (headA && headB) { if (headA === headB) { return headA; } headA = headA.next; headB = headB.next; } return null; };

hon9g commented 4 years ago

19. Remove Nth Node From End of List

🌐problem
Two Pointer

algorithm
1. To remove n-th node from the end, send node hare as far as n.
2. Move node curr and hare in same speed until hare gets the last node.
3. Since curr and hare has gap as n, curr has n+1-th node from the end when hare has 1th node from the end. So change curr.next to curr.next.next.

edge case n = 3 linked list = [1,2,3]

When n is same with the length of the list. We need to remove first element, instead remove next element of curr.
In this case, you can find that hare would be null, because the last element of list points null such as [1,2,3,null]

complexity

Time complexity: O(N)

Space complexity: O(1)

/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
let hare = head, curr = head;
while (n--) {
    hare = hare.next;
}
while (hare && hare.next) {
    curr = curr.next;
    hare = hare.next;
}
if (!hare) {
    head = head.next;
} else {
    curr.next = curr.next ? curr.next.next : null;
}
return head;
};

hon9g commented 4 years ago

206. Reverse Linked List

🌐problem
Reverse Pointers
Time complexity: O(N)

Space complexity: O(1)

/**
* @param {ListNode} head
* @return {ListNode}
*/
const reverseList = (head, prev=null) => {
while (head) [head.next, prev, head] = [prev, head, head.next];
return prev;
};

/**
* @param {ListNode} head
* @return {ListNode}
*/
const reverseList = (head) => {
let prev = null, next = null;
while (head) {
    next = head.next;
    head.next = prev;
    prev = head;
    head = next;
}
return prev;
};

Time complexity: O(N)
Space complexity: O(N) because of call stack

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const reverseList = (head, prev=null) => {
    if (!head) return prev;
    [head.next, prev, head] = [prev, head, head.next]; 
    return reverseList(head, prev);
};

hon9g commented 4 years ago

203. Remove Linked List Elements

🌐problem
Time complexity: O()

Space complexity: O()

/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
const removeElements = (head, val) => {
let prev = null, curr = head;
while (curr) {
    if (curr.val === val) {
        if (prev) {
            prev.next = curr.next;
        } else {
            head = curr.next;
        }
    } else {
        prev = curr;
    }
    curr = curr.next;
}
return head;
};

hon9g commented 4 years ago

328. Odd Even Linked List

🌐problem
Time complexity: O(N)

Space complexity: O(1)

/**
* @param {ListNode} head
* @return {ListNode}
*/
const oddEvenList = head => {
if (!head) return null;
const head2 = head.next;
let odd = head, even = null;
while (odd.next) {
    even = odd.next;
    odd.next = odd.next ? odd.next.next : null;
    if (!odd.next) break;
    even.next = even.next ? even.next.next : null;
    odd = odd.next;
}
odd.next = head2;
return head;  
};

hon9g commented 4 years ago

234. Palindrome Linked List

🌐problem
Move values into the Array
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {ListNode} head
* @return {boolean}
*/
const isPalindrome = function(head) {
const a = [];
while (head) {
    a.push(head.val);
    head = head.next;
}
const b = a.slice().reverse();
for (let i = 0; i < a.length; i++) {
    if (a[i] !== b[i]) {
        return false;
    }
}
return true;
};

Remove Tails

Time complexity: O(N^2)

Space complexity: O(N) because of call stack

const reversed = (head, prev) => {
if (!head.next) {
    const n = head.val;
    if (prev) prev.next = null;
    return n;
};
return reversed(head.next, head);
}
/**
* @param {ListNode} head
* @return {boolean}
*/
const isPalindrome = function(head) {
while (head) {
    if (head.val !== reversed(head, null)) {
        return false;
    }
    head = head.next;
}
return true;
};

hon9g commented 4 years ago

21. Merge Two Sorted Lists

🌐problem
Time complexity: O(min(N,M))

Space complexity: O(1) Its about extra space. It use N space for result itself


/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
const mergeTwoLists = function(l1, l2) {
const head = new ListNode(null);
let curr = head;
while (l1 && l2) {
    if (l1.val < l2.val) {
        curr.next = l1;
        l1 = l1.next;
    } else {
        curr.next = l2;
        l2 = l2.next;
    }
    curr = curr.next;
}
curr.next = l1 || l2;
return head.next;

};


```Python
class Solution:
    def mergeTwoLists(self, N, M):
        head = curr = ListNode(0)
        while N and M:
            if N.val < M.val:
                curr.next, N = N, N.next
            else:
                curr.next, M = M, M.next
            curr = curr.next
        curr.next = N or M
        return head.next

hon9g commented 4 years ago

2. Add Two Numbers

🌐problem
Time complexity: O(N+M)

Space complexity: O(1) Its about extra space, It use N space for result itself

/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
const addTwoNumbers = (l1, l2) => {
const head = new ListNode(null);
let curr = head, carry = 0;
while (l1 && l2) {
    const n = l1.val + l2.val + carry;
    curr.next = new ListNode(n%10);
    carry = parseInt(n/10);
    curr = curr.next, l1 = l1.next, l2 = l2.next;
}
while (l1 || l2) {
    const n = l1 ? l1.val + carry : l2.val + carry;
    curr.next = new ListNode(n%10);
    carry = parseInt(n/10);
    curr = curr.next;
    l1 ? l1 = l1.next : l2 = l2.next;
}
if (carry) {
    curr.next = new ListNode(carry);
}
return head.next;
};

hon9g commented 4 years ago

430. Flatten a Multilevel Doubly Linked List

🌐problem
Stack
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {Node} head
* @return {Node}
*/
const flatten = function(head) {
let curr = head;
const nexts = [];
while (curr) {
    if (curr.child) {
        const child = curr.child;
        curr.child = null;
        child.prev = curr;
        if (curr.next) {
            nexts.push(curr.next);
        }
        curr.next = child;
    }
    if (nexts.length && !curr.next) {
        const next = nexts.pop();
        next.prev = curr;
        curr.next = next;
    }
    curr = curr.next;
}
return head;
};

hon9g commented 4 years ago

708. Insert into a Sorted Circular Linked List

🌐problem
One Loop
Time complexity: O(N)

Space complexity: O(1)

/**
* @param {Node} head
* @param {number} insertVal
* @return {Node}
*/
const insert = (head, insertVal) => {
if (!head) {
    const head = new Node(insertVal);
    head.next = head;
    return head;
}
let curr = head, flag = false;
while (true) {
    if ((curr.next.val >= insertVal && curr.val < insertVal)
         ||(curr.next.val >= insertVal && curr.val > curr.next.val)
         ||(curr.val <= insertVal && curr.val > curr.next.val)) {
        flag = true;
        break;
    }
    if (head === curr.next) {
        break;
    }
    curr = curr.next;
}
curr.next = new Node(insertVal, curr.next);
return head;
};

/**
* @param {Node} head
* @param {number} insertVal
* @return {Node}
*/
const insert = function(head, insertVal) {
if (!head) {
    const head = new Node(insertVal);
    head.next = head;
    return head;
};
let curr = head;
while (curr) {
    if (curr.next === head) {
        curr.next = null;
    }
    curr = curr.next;
}
curr = head;
while (curr.next) {
    if((curr.next ? curr.next.val >= insertVal && curr.val < insertVal : curr.val < insertVal)
        ||(curr.next ? curr.next.val >= insertVal && curr.val > curr.next.val : false)
        ||(curr.val <= insertVal && curr.val > curr.next.val)) {
        break;
    }
    curr = curr.next;
}
curr.next = new Node(insertVal, curr.next);
while (curr.next) {
    curr = curr.next;
}
curr.next = head;
return head;
};

hon9g commented 4 years ago

138. Copy List with Random Pointer

🌐problem
Two pass
Time complexity: O(N)

Space complexity: O(N)

/**
* @param {Node} head
* @return {Node}
*/
const copyRandomList = (head) => {
const seen = new Map();
let curr = head;
while (curr) {
    seen.set(curr, new Node(curr.val));
    curr = curr.next;
}
curr = head;
while (curr) {
    seen.get(curr).next = curr.next ? seen.get(curr.next) : null;
    seen.get(curr).random = curr.random ? seen.get(curr.random) : null;
    curr = curr.next;
}
return head ? seen.get(head) : null;
};

One pass

Time complexity: O(N)

Space complexity: O(N)

/**
* @param {Node} head
* @return {Node}
*/
const copyRandomList = (head) => {
const seen = new Map();
let curr = head;
if (head) seen.set(head, new Node(head.val));
while (curr) {
    if (curr.next) {
        if (!seen.has(curr.next)) {
            seen.set(curr.next, new Node(curr.next.val));
        }
        seen.get(curr).next = seen.get(curr.next);
    }
    if (curr.random) {
        if (!seen.has(curr.random)) {
            seen.set(curr.random, new Node(curr.random.val));
        }
        seen.get(curr).random = seen.get(curr.random);
    }
    curr = curr.next;
}
return head ? seen.get(head) : null;
};

hon9g commented 4 years ago

61. Rotate List

🌐problem
K iterative
Time complexity: O(K)

Space complexity: O(1)

/**
* @param {ListNode} head
* @param {number} k
* @return {ListNode}
*/
var rotateRight = function(head, k) {
if (!head) return head;
let tortoise = head, hare = head;
while (k--) {
    hare = hare.next;
    if (!hare) hare = head;
}
while (hare && hare.next) {
    hare = hare.next;
    tortoise = tortoise.next;
}
if (hare !== head) {
    hare.next = head;
    head = tortoise.next;
    tortoise.next = null;
}
return head;
};

hon9g / algorithms

Linked List #27

🔗 Singly Linked List

🔗 Two Pointer Technique

🔗 Classic Problems

🔗 Doubly Linked List

🔗 Conclusion

707. Design Linked List

Singly Linked List

141. Linked List Cycle

Hash Set

Two Pointer

Change values

142. Linked List Cycle II

Hash Set

Floyd's Tortoise and Hare

160. Intersection of Two Linked Lists

Hash Set

Floyd's Tortoise and Hare algorithm

Different Counts of Nodes

19. Remove Nth Node From End of List

Two Pointer

206. Reverse Linked List

Reverse Pointers

203. Remove Linked List Elements

328. Odd Even Linked List

234. Palindrome Linked List

Move values into the Array

Remove Tails

21. Merge Two Sorted Lists

2. Add Two Numbers

430. Flatten a Multilevel Doubly Linked List

Stack

708. Insert into a Sorted Circular Linked List

One Loop

138. Copy List with Random Pointer

Two pass

One pass

61. Rotate List

K iterative