Linked list in Python

Posted on Edited on In , Views:

Intro

A linked list is a data structure which represents a sequence of nodes. In a singly linked list, each node points to the next node. In a doubly linked list, each node points to both the next and previous node.

[Leetcode 25] Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Example 1:

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

Example 2:

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

Constraints:

  • The number of nodes in the list is n.
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # check if reverse is needed
        curr = head
        for _ in range(k):
            if not curr:
                return head # no need to reverse, thus return the original head
            curr = curr.next

        # Reverse the sub-list with k nodes
        # e.g.
        # None  1 -> 2 -> 3 -> 4 -> 5 -> 6, k = 3
        # ^     ^
        # prev  head(curr) 
        #
        # After reverse the first 3 nodes,
        # 3 -> 2 -> 1 -> 4 -> 5 -> 6
        # ^         ^    ^
        # prev      head curr
        prev, curr = None, head
        for _ in range(k):
            next = curr.next # save the next before we break the pointer
            curr.next = prev # point to previous node(reverse)
            prev = curr # shift previous pointer
            curr = next # shift current pointer 

        # after reverse, the curr pointer points to the "head" of next k nodes, 
        # and the previous pointer points to the new "head" of the reversed k nodes.
        head.next = self.reverseKGroup(curr, k) 

        # the previous pointer points to the head of reversed list
        return prev

[Leetcode 82] Remove Duplicates from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

Example 1:

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

Example 2:

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

Constraints:

  • The number of nodes in the list is in the range [0, 300].
  • -100 <= Node.val <= 100
  • The list is guaranteed to be sorted in ascending order.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        dummy = ListNode()
        dummy.next = head
        prev = dummy

        while head and head.next:
            if head.val == head.next.val:
                while head and head.next and head.val == head.next.val:
                    head = head.next

                head = head.next # move to next node which has different value
                prev.next = head # point previous to the new node
            else:
                prev = prev.next
                head = head.next

        return dummy.next

[Leetcode 92] Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

1
2
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

1
2
Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

  • The number of nodes in the list is n.
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        mthNode = head

        i = 1
        while i < left:
            prev = mthNode
            mthNode = mthNode.next
            i += 1

        nthNode = mthNode
        while i < right:
            nthNode = nthNode.next
            i += 1

        # disconnect prev and first node
        prev.next = None

        # disconnect last node and its next
        second = nthNode.next
        nthNode.next = None

        # reverse list between first and last node
        curr = mthNode
        tempHead = curr
        while curr.next:
            temp = curr.next
            curr.next = curr.next.next

            temp.next = tempHead
            tempHead = temp

        # connect prev and new head of reversed list
        prev.next = tempHead

        # connect the new last node and second half list
        curr.next = second

        return dummy.next

[Leetcode 138] Copy List with Random Pointer

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked 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) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

1
2
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

1
2
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

1
2
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

  • 0 <= n <= 1000
  • -10^4 <= Node.val <= 10^4
  • Node.random is null or is pointing to some node in the linked list.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        oldToNew = {}

        # copy a new node for each original node
        curr = head
        while curr:
            oldToNew[curr] = Node(curr.val)
            curr = curr.next

        curr = head
        while curr:
            # get() returns None if the key doesn't exist
            oldToNew[curr].next = oldToNew.get(curr.next) 
            oldToNew[curr].random = oldToNew.get(curr.random)
            curr = curr.next

        return oldToNew[head]

[Leetcoe 146] LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls will be made to get and put.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class LRUCache:
    # double-linked list
    class Node:
        def __init__(self, key=None, val=None):
            self.key = key
            self.val = val
            self.next = None
            self.prev = None

    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}

        # dummy head and tail for the doubled-linked list
        self.head = self.Node()
        self.tail = self.Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def addNode(self, node):
        node1 = self.head.next
        node.next = node1
        node1.prev = node
        self.head.next = node
        node.prev = self.head

    def deleteNode(self, node):
        prev = node.prev
        next = node.next
        prev.next = next
        next.prev = prev

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            val = node.val
            del self.cache[key]
            self.deleteNode(node)
            self.addNode(node)
            self.cache[key] = self.head.next
            return val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            del self.cache[key]
            self.deleteNode(node)

        # delete the least recently used node when the capacity is full
        if len(self.cache) == self.cap:
            del self.cache[self.tail.prev.key]
            self.deleteNode(self.tail.prev)

        # insert the most recent used node to the front
        self.addNode(self.Node(key, value))
        self.cache[key] = self.head.next


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

[Leetcode 206] Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

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

Example 2:

1
2
Input: head = [1,2]
Output: [2,1]

Example 3:

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

Constraints:

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

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    # Time: O(n) Space: O(1)
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head
        while curr:
            next = curr.next # save next node before we break the pointer
            curr.next = prev # point to previous node
            prev = curr # shift previous pointer 
            curr = next # shift current pointer

        return prev

    # Time: O(n) Space: O(1)
    def reverseList_recursive(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        # e.g.
        #   1 -> 2 -> 3 -> 4
        #   ^    ^
        # head  head.next
        #
        #   4  ->  3  ->  2    ->     1   -> None
        #   ^             ^           ^
        # newHead        head.next   head
        newHead = head
        if head.next:
            newHead = self.reverseList(head.next)
            head.next.next = head
        head.next = None

        return newHead

[Leetcode 2130] Maximum Twin Sum of a Linked List

In a linked list of size n, where n is even, the ith node (0-indexed) of the linked list is known as the twin of the (n-1-i)th node, if 0 <= i <= (n / 2) - 1.

  • For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

1
2
3
4
5
6
7
8
5-->4-->2-->1
0   1   2   3
Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.

Constraints:

  • The number of nodes in the list is an even integer in the range [2, 105].
  • 1 <= Node.val <= 105

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        slow = fast = head

        # get the middle of linked list
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # reverse the second half of linked list
        prev, curr = None, slow
        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next

        # get twin max sum
        maxVal = 0
        while prev:
            maxVal = max(maxVal, head.val + prev.val)
            head = head.next
            prev = prev.next

        return maxVal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        st = []
        
        slow = fast = head
        st.append(slow.val)

        while fast and fast.next and fast.next.next:   
            slow = slow.next
            st.append(slow.val)
            fast = fast.next.next

        maxTwinSum = 0
        slow = slow.next
        while st:
            twinSum = slow.val + st.pop()
            maxTwinSum = max(maxTwinSum, twinSum)
            slow = slow.next

        return maxTwinSum