Linked Lists

2. Add Two Numbers

https://leetcode.com/problems/add-two-numbers/

Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution

https://leetcode.com/problems/add-two-numbers/solution/

https://leetcode.com/problems/add-two-numbers/discuss/1032/Python-concise-solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = cur = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            if l1:
                carry += l1.val
                l1 = l1.next
            if l2:
                carry += l2.val
                l2 = l2.next
            cur.next = ListNode(carry%10)
            cur = cur.next
            carry //= 10
        return dummy.next

19. Remove Nth Node From End of List[M]

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Description

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

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Solution

https://leetcode.com/problems/remove-nth-node-from-end-of-list/solution/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        slow = fast = head
        for i in range(n):
            fast = fast.next
        if fast is None:
            head = head.next
            return head
        while fast.next is not None:
            fast = fast.next
            slow = slow.next
        curr = slow.next
        slow.next = curr.next
        return head

21. Merge Two Sorted Lists[E]

Description

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:

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

Solution

https://leetcode.com/problems/merge-two-sorted-lists/discuss/9735/Python-solutions-(iteratively-recursively-iteratively-in-place).

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
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # if l1 is None:
        #     return l2
        # if l2 is None:
        #     return l1
        head = curr = ListNode(-1)
        while l1 is not None and l2 is not None:
            if l1.val <= l2.val:
                curr.next = l1
                l1 = l1.next
            else:
                curr.next = l2
                l2 = l2.next
            curr = curr.next
        if l1 is not None:
            curr.next = l1
        if l2 is not None:
            curr.next = l2
        return head.next

23. Merge k Sorted Lists[H]

https://leetcode.com/problems/merge-k-sorted-lists/

Description

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

1
2
3
4
5
6
7
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution

1

24. Swap Nodes in Pairs

https://leetcode.com/problems/swap-nodes-in-pairs/

Description

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

1
Given 1->2->3->4, you should return the list as 2->1->4->3.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummyHead = ListNode(-1)
        dummyHead.next = head
        prev, p = dummyHead, head
        while p != None and p.next != None:
            q, r = p.next, p.next.next
            prev.next = q
            q.next = p
            p.next = r
            prev = p
            p = r
        return dummyHead.next

1

25. Reverse Nodes in k-Group[H]

https://leetcode.com/problems/reverse-nodes-in-k-group/

Description

Given a linked list, reverse the nodes of a linked list k at a time and return its 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.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

  • Only constant extra memory is allowed.
  • You may not alter the values in the list’s nodes, only nodes itself may be changed.

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
# 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: ListNode, k: int) -> ListNode:
        if head is None:
            return None
        index = 0
        lead, last = 0, 0
        pos = head
        temp = ListNode(-1)
        temp.next = head
        head = temp
        start = head
        while pos is not None:
            if index % k == k - 1:
                last = pos.next
                start = self.reverseList(start, last)
                pos = start
            pos = pos.next
            index += 1
        return head.next

    def reverseList(self, head, end):
        pos = head.next
        last = end
        next_start = pos
        while pos != end:
            head.next = pos
            last_pos = pos
            pos = pos.next
            last_pos.next = last
            last = last_pos
        return next_start

61. Rotate List[M]

https://leetcode.com/problems/rotate-list/

Description

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

1
2
3
4
5
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

1
2
3
4
5
6
7
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Solution

1

92. Reverse Linked List II[M]

https://leetcode.com/problems/reverse-linked-list-ii/

Description

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

Example:

1
2
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

Solution

1

141. Linked List Cycle[E]

https://leetcode.com/problems/linked-list-cycle/

Description

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

img

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

img

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

img

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Solution

https://leetcode.com/problems/linked-list-cycle/solution/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        try:
            fast = head.next.next
            slow = head.next

            while fast != slow:
                fast = fast.next.next
                slow = slow.next

            return True
        except:
            return False

142. Linked List Cycle II[M]

https://leetcode.com/problems/linked-list-cycle-ii/

Description

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

img

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

img

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

img

Follow-up:
Can you solve it without using extra space?

Solution

https://discuss.leetcode.com/topic/2975/o-n-solution-by-using-two-pointers-without-change-anything

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:e: ListNode
        try:
            fast = head.next.next
            slow = head.next

            while fast != slow:
                fast = fast.next.next
                slow = slow.next
        except:
            return None
        slow = head
        while fast != slow:
            fast = fast.next
            slow = slow.next
        return fast

160. Intersection of Two Linked Lists[E]

https://leetcode.com/problems/intersection-of-two-linked-lists/

Description

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

For example, the following two linked lists:

img

begin to intersect at node c1.

Example 1:

img

1
2
3
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

img

1
2
3
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

img

1
2
3
4
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Each value on each linked list is in the range [1, 10^9].
  • Your code should preferably run in O(n) time and use only O(1) memory.

Solution

https://leetcode.com/articles/intersection-two-linked-lists/

https://leetcode.com/problems/intersection-of-two-linked-lists/solution/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        a, b = headA, headB
        ans = None
        while a or b:
            if not a:
                a = headB
            if not b:
                b = headA
            if a == b and not ans:
                ans = a
            a, b = a.next, b.next
        return ans

203. Remove Linked List Elements[E]

https://leetcode.com/problems/remove-linked-list-elements/

Description

Remove all elements from a linked list of integers that have value *val*.

Example:

1
2
Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        prehead = ListNode(-1)
        prehead.next = head
        last, pos = prehead, head
        while pos is not None:
            if pos.val == val:
                last.next = pos.next
            else:
                last = pos
            pos = pos.next
        return prehead.next

206. Reverse Linked List[E]

https://leetcode.com/problems/reverse-linked-list/

Description

Reverse a singly linked list.

Example:

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

Follow up:

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

Solution

1

237. Delete Node in a Linked List[E]

https://leetcode.com/problems/delete-node-in-a-linked-list/

Description

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Given linked list – head = [4,5,1,9], which looks like following:

img

Example 1:

1
2
3
Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

1
2
3
Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Note:

  • The linked list will have at least two elements.
  • All of the nodes’ values will be unique.
  • The given node will not be the tail and it will always be a valid node of the linked list.
  • Do not return anything from your function.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        node.val = node.next.val
        node.next = node.next.next

328. Odd Even Linked List[M]

https://leetcode.com/problems/odd-even-linked-list/

Description

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.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

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

Example 2:

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

Constraints:

  • The relative order inside both the even and odd groups should remain as it was in the input.
  • The first node is considered odd, the second node even and so on …
  • The length of the linked list is between [0, 10^4].

Solution

1

876. Middle of the Linked List[E]

https://leetcode.com/problems/middle-of-the-linked-list/

Description

Given a non-empty, singly linked list with head node head, return a middle node of linked list.

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

Example 1:

1
2
3
4
5
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:

1
2
3
Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:

  • The number of nodes in the given list will be between 1 and 100.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        fast = slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

143. Reorder List[M]]

https://leetcode.com/problems/reorder-list/

Description

Given a singly linked list L: L0→L1→…→L**n-1→Ln,
reorder it to: L0→L**n→L1→L**n-1→L2→L**n-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

1
Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

1
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

Solution

1

138. Copy List with Random Pointer[M]

https://leetcode.com/problems/copy-list-with-random-pointer/

Description

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.

Example 1:

img

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:

img

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

Example 3:

img

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

Example 4:

1
2
3
Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

  • -10000 <= Node.val <= 10000
  • Node.random is null or pointing to a node in the linked list.
  • Number of Nodes will not exceed 1000.

Solution

1

147. Insertion Sort List[M]

https://leetcode.com/problems/insertion-sort-list/

Description

ort a linked list using insertion sort.

img
A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.
With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

  1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
  2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
  3. It repeats until no input elements remain.

Example 1:

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

Example 2:

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

Solution

1

83. Remove Duplicates from Sorted List[E]

https://leetcode.com/problems/remove-duplicates-from-sorted-list/

Description

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

1
2
Input: 1->1->2
Output: 1->2

Example 2:

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

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 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: ListNode) -> ListNode:
        if head is None:
            return None
        pos = head
        while pos is not None and pos.next is not None:
            if pos.val == pos.next.val:
                pos.next = pos.next.next
            else:
                pos = pos.next
        return head

86. Partition List[M]

https://leetcode.com/problems/partition-list/

Description

iven 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.

Example:

1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Solution

https://leetcode.com/problems/partition-list/solution/

1