Singly Linked Lists

[sophryu99]

Initialization of singly-linked list

# Definition for singly-linked list.
class ListNode:
     def __init__(self, x):
         self.val = x
         self.next = None

Big-O

• O(n) for access and search
• O(1) for insertion and deletion

[sophryu99]

Deleting node of a Linked List at certain node

Logic

• Store the head's next node to a variable
• Replace current head with the next node

class Solution:
    def deleteNode(self, node):
        next_ = node.next
        node.val = next_.val
        node.next = next_.next

[sophryu99]

Removing nth node from the end

Logic

• Traverse through the Linked List to count the total heads
• Traverse through the Linked List again to reach the nth node from the end
• Replace the head's next node with next.next node.

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        left = head
        node_count = 1
        
        while left:
            if left.next:
                node_count += 1
                left = left.next
            else:
                break
        
        base = head
        nth = node_count - n - 1
        cnt = 0
        if nth + 1 <= 0:
            base = base.next
            return base
            
        while base:
            if cnt == nth:
                base.next = base.next.next
                break
            base = base.next
            cnt += 1
            
        return (head)
            

[sophryu99]

Traversing Through LL and storing the values

def store(lnode):
            vals = []
            while lnode:
                vals.append(lnode.val)
                lnode = lnode.next
            return vals[::-1]