Singly Linked List

 

Singly Linked List: A Singly Linked List is a data structure where each element (node) contains a value and a reference to the next node in the list. The last node points to None, indicating the end of the list. The main operations supported by a Singly Linked List are insertion at the beginning, insertion at the end, deletion of a node, and traversal.

Problem Statement: Given a Singly Linked List, find the middle element. If the list has an even number of elements, return the second middle element.

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

To solve this problem, we'll use the "two-pointer" approach. We'll have two pointers, one moving at double the speed of the other. When the faster pointer reaches the end of the list, the slower pointer will be pointing to the middle element.

Here's the complete code to implement a Singly Linked List class and solve the problem:


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class LinkedList:
    def __init__(self):
        self.head = None

    def insert_at_end(self, val):
        new_node = ListNode(val)

        if not self.head:
            self.head = new_node
        else:
            curr = self.head
            while curr.next:
                curr = curr.next
            curr.next = new_node

    def find_middle_element(self):
        if not self.head:
            return None

        slow = self.head
        fast = self.head

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

        return slow.val


# Example usage
# Create a linked list with nodes [1, 2, 3, 4, 5]
ll = LinkedList()
ll.insert_at_end(1)
ll.insert_at_end(2)
ll.insert_at_end(3)
ll.insert_at_end(4)
ll.insert_at_end(5)

# Find the middle element of the linked list
middle_element = ll.find_middle_element()
print(middle_element)

In this code, we first define a ListNode class to represent a node in the linked list. Each node has a val attribute to store the value and a next attribute to point to the next node in the list.

Next, we define a LinkedList class to represent the Singly Linked List. It has a head attribute to store the reference to the first node in the list. The class provides a method insert_at_end to insert a new node at the end of the list and a method find_middle_element to find the middle element of the list using the two-pointer approach.

We create a LinkedList object, insert nodes with values [1, 2, 3, 4, 5] at the end, and then call the find_middle_element method to retrieve the middle element. In this case, the output will be 3.

Time and Space Complexity Analysis: The time complexity of finding the middle element in a Singly Linked List using the two-pointer approach is O(N), where N is the number of nodes in the list. We traverse the list once, with the faster pointer moving at double the speed of the slower pointer.

The space complexity is O(1) since we only use a constant amount of additional space to store the two pointers.

Let's solve a question from LeetCode using the concept of a Singly Linked List. The problem we'll solve is "Reverse Linked List," which asks us to reverse a given linked list.

Problem Statement: Given the head of a singly linked list, reverse the list and return the new head.

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

To solve this problem, we'll iterate through the linked list and reverse the links between nodes. We'll maintain three pointers: prev, curr, and next. At each step, we'll update the next pointer to keep track of the next node, set the curr node's next pointer to the prev node, and move all pointers one step forward. This process continues until we reach the end of the list.

Here's the complete code to reverse a singly linked list:


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_linked_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev


# Example usage
# Create a linked list with nodes [1, 2, 3, 4, 5]
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# Reverse the linked list
new_head = reverse_linked_list(head)

# Print the reversed linked list
curr = new_head
while curr:
    print(curr.val, end=" -> ")
    curr = curr.next
print("None")

In this code, we define a ListNode class to represent a node in the linked list. Each node has a val attribute to store the value and a next attribute to point to the next node in the list.

The reverse_linked_list function takes the head of the linked list as input and reverses the list by modifying the links between nodes. We start with prev and curr both pointing to None. Then, we iterate through the list, updating the links and moving the pointers accordingly. Finally, we return the new head of the reversed list.

We create a linked list with nodes [1, 2, 3, 4, 5], then call the reverse_linked_list function to reverse the list. We print the reversed list to verify the result.

Time and Space Complexity Analysis: The time complexity of reversing a singly linked list using the iterative approach is O(N), where N is the number of nodes in the list. We iterate through each node once.

The space complexity is O(1) since we only use a constant amount of additional space to store the pointers prev, curr, and next_node.

 

 

 

Next Post Previous Post