Linked List Algorithm

Question 1

83. Remove Duplicates from Sorted List
    Easy

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

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

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

Answer 1

Time Complexity: O(n)

class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
         # remember that this is for checking for None type that would normally be handled with a dummy node
        while cur and cur.next:
            if cur.val == cur.next.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

Space Complexity: O(1)

Question 2

206. Reverse Linked List
     Easy

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

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

Answer 2

Time Complexity: O(n)

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        prev = None
        
        while cur:
            temp = cur.next
            cur.next = prev
            prev = cur
            cur = temp
        
        return prev

Space Complexity: O(1)

Question 3

141. Linked List Cycle

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false

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

Easy - Floyd’s Algorithm

Answer 3

Time Complexity: O(n)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        dummy = ListNode()
        dummy.next = head
        slow = fast = dummy

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

            if slow is fast:
                return True

        return False

Space Complexity: O(1)

Question 4

2 1. Merge Two Sorted Lists
Easy

Topics
Companies
You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

https://leetcode.com/problems/merge-two-sorted-lists/description/

Answer 4

Time Complexity: O(n)

Definition for singly-linked list.
# class ListNode(object):
#     def \_\_init\_\_(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        d = ListNode()
        cur = d

        while list1 and list2:
            if list1.val < list2.val:
						    # updates the previous value's next with the current list with the lesser val. This will cover all cases up until the last, which is handled before the return but after the loop. Remember if you mess up the order of cur.next and cur, you'll move curr to the next node before you can assign the previous node's next
                cur.next = list1
                cur = list1
                list1 = list1.next
            else:
                cur.next = list2
                cur = list2
                list2 = list2.next

        cur.next = list1 if list1 else list2

        return d.next

Question 5

19. Remove Nth Node From End of List
    Medium

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

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

https://algomap.io/

Answer 5

Time Complexity: O(n)

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        behind = ahead = dummy

        for _ in range(n + 1):
            ahead = ahead.next

        while ahead:
            behind = behind.next
            ahead = ahead.next

        behind.next = behind.next.next

        return dummy.next

Time Complexity: O(n)
# Space Complexity: O(1)

Question 6

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.

Output: [[7,null],[1

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

https://leetcode.com/problems/copy-list-with-random-pointer/description/
https://www.youtube.com/watch?v=DAzEniVtkMQ

Answer 6

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        curr = head
         
        o_t_n = {}

        while curr:
            node = Node(x=curr.val)
            o_t_n[curr] = node
            curr = curr.next

        curr = head

        while curr:
            node = o_t_n[curr]
            node.next = o_t_n[curr.next] if curr.next else None
            node.random = o_t_n[curr.random] if curr.random else None
            curr = curr.next

        return o_t_n[head] 

        # Time: O(n)
        # Space: O(n)

Question 7

Reorder list

Answer 7

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        fast = head
        slow = head

        # Step 1: Find the middle of the list
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # Step 2: Reverse the second half of the list
        second = slow.next
        slow.next = None
        node = None

        while second:
            temp = second.next
            second.next = node
            node = second
            second = temp

        # Step 3: Merge the two halves
        first = head
        second = node

        while second:
            temp1, temp2 = first.next, second.next
            first.next, second.next = second, temp1
            first, second = temp1, temp2