linked list

Question 1

delete the middle node of a linked list
intuition

Answer 1

Base Case Check:
- If head is null, the list is empty. The method returns null since there’s nothing to delete.

**Initialization: **
- A dummy node, prev, is created and its next pointer is set to head. This dummy node serves as a placeholder to simplify edge case handling, especially when the list has only one node or when we need to delete the first real node of the list.
- Two pointers, slow and fast, are initialized: slow starts at prev and fast starts at head.

Traversal:
- The list is traversed using the two-pointer technique where fast moves twice as fast as slow. For every move fast makes two steps (if possible), slow makes one step.
- This traversal continues until fast reaches the end of the list (fast is null) or fast is at the last node (fast.next is null). At this point, slow will be just before the middle node of the list. This is because while fast moves through the entire list, slow moves only half the distance.

Deletion:
- Once the traversal is complete, slow is either at the node just before the middle of the list (for odd-length lists) or at the node before the second middle node (for even-length lists, where there are two middle nodes, and the first one is considered the middle for deletion).
- The middle node is then removed by adjusting the next pointer of the slow node to skip over the middle node and point directly to the node after the middle node. This effectively removes the middle node from the list.

Return:
- Finally, the method returns the new list, but since the prev node was a dummy node added at the start, the method returns prev.next to return the actual head of the modified list.

Question 2

delete the middle node of a linked list
code

Answer 2

def deleteMiddle(head):
    """
    :type head: Optional[ListNode]
    :rtype: Optional[ListNode]
    """
    if head == None :return None
    prev = ListNode(0)
    prev.next = head
    slow = prev
    fast = head
    while fast != None and fast.next != None:
        slow = slow.next
        fast = fast.next.next
    
    slow.next = slow.next.next
    return prev.next

Question 3

odd even linked list
intuition

Answer 3

Base Case Handling: The code first checks if the input list is either empty (head == null) or contains only one node (head.next == null). In either case, the list doesn’t need rearranging, so the original head of the list is returned immediately.

Dummy Head Initialization: Two dummy head nodes, odd and even, are created. These nodes serve as the starting points for two separate lists: one to collect all nodes from odd positions and the other for nodes from even positions. This is a common technique used to simplify list manipulation by avoiding dealing with special cases for the head node.

**Pointer Initialization: **Two pointers, odd_ptr and even_ptr, are initialized to point to the respective dummy heads. These pointers will traverse the lists, allowing new nodes to be appended to the respective odd and even lists.

List Traversal and Node Classification: The code enters a loop that continues until all nodes from the original list (head) have been processed. Within the loop, an index variable is used to determine whether the current node is at an odd or even position:

• If index is odd, the current node belongs to the odd list, so it’s appended to the list that odd_ptr is building. odd_ptr is then advanced to this newly added node.
• If index is even, a similar process is followed for the even list using even_ptr.

Linking Odd and Even Lists: After all nodes have been classified and the original list has been fully traversed, the code performs two crucial steps to finalize the rearrangement:

• The end of the even list is marked by setting even_ptr.next to null. This ensures the even list is properly terminated and doesn’t inadvertently link back to any nodes that might follow it in memory.
• The odd and even lists are concatenated. This is done by setting the next pointer of the last node in the odd list (odd_ptr.next) to point to the first real node in the even list (even.next), effectively skipping the even dummy head.

Returning the Result: Finally, the method returns odd.next, which points to the first real node in the odd list, effectively skipping the odd dummy head. This is the new head of the rearranged list where all odd-positioned nodes are followed by all even-positioned nodes.

Question 4

odd even linked list
code

Answer 4

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 oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None : return head 
        odd = ListNode(0) 
        odd_ptr = odd
        even = ListNode(0)
        even_ptr = even 
        idx = 1 
        while head != None :
            if idx % 2 == 0:
                even_ptr.next = head
                even_ptr = even_ptr.next
            else:
                odd_ptr.next = head
                odd_ptr = odd_ptr.next
            head = head.next
            idx+=1
        even_ptr.next = None
        odd_ptr.next = even.next
        return odd.next

Question 5

reverse linked list
intuition

Answer 5

Assume that we have linked list 1 → 2 → 3 → Ø, we would like to change it to Ø ← 1 ← 2 ← 3.

While traversing the list, we can change the current node’s next pointer to point to its previous element. Since a node does not have reference to its previous node, we must store its previous element beforehand. We also need another pointer to store the next node before changing the reference. Do not forget to return the new head reference at the end!

Question 6

reverse linked list
code

Answer 6

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
            
        return prev

Question 7

maximum twin sum of a linked list
intuition

Answer 7

1. Create a ListNode pointer current. Initialize it equal to head.
2. Initialize an integer stack st to store the node values in the given linked list.
3. Iterate while current is not null:
   - Push current.val into st.
   - Update current to current.next.
4. Update current to head to iterate the list again from the start.
5. To begin counting the number of twin pairs, create two integers size = st.size() and count. To cover all the twin pairs, we start counting from 1 and go until st.size() / 2.
6. Create an answer variable maximumSum to keep track of the maximum sum of a node and its twin. Initialize it to 0.
7. While count <= size/2:
   - Update maximumSum if the current twin sum is greater than the previous one, i.e.,maximumSum = max(maximumSum, current.val + st.top()).
   - Update current to current.next.
   - Pop the top element out of the stack.
   - Increment count by 1.
8. Return maximumSum.

Question 8

maximum twin sum of a linked list
code

Answer 8

class Solution(object):
    def pairSum(self, head):
        current = head
        st = []
        maximumSum = 0

        while current:
            st.append(current.val)
            current = current.next

        current = head
        size = len(st)
        count = 1
        maximumSum = 0
        while count <= size/2:
            maximumSum = max(maximumSum, current.val + st.pop())
            current = current.next
            count = count + 1

        return maximumSum