Linked List Problems (C, C++, Java)

Solution and explanation

Solution

After slow and fast meet, move slow back to head and advance both one step at a time; they meet again exactly at the start of the cycle.

Why it works

Let a = distance from head to the cycle start, b = distance from the start to the meeting point, c = cycle length. fast travelled twice as far as slow: 2(a + b) = a + b + k·c, so a = k·c − b. Walking a steps from the head and a steps from the meeting point therefore lands both pointers on the cycle start.

Example

10 → 20 → 30 → 40 → 50 → 30: the cycle starts at 30.

Complexity

• O(n) time, O(1) space.

Solution and explanation

Complexity

Expected output

Original: 10 -> 20 -> 30 -> 40 -> 50 -> NULL
Q21 Middle: 30
Q22 Reversed iteratively: 50 -> 40 -> 30 -> 20 -> 10 -> NULL
Q23 Reversed recursively: 10 -> 20 -> 30 -> 40 -> 50 -> NULL
Q24 Has cycle: Yes
Q25 Cycle starts at: 30

C

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node* createNode(int value) {
    Node *n = malloc(sizeof(Node));
    if (!n) exit(EXIT_FAILURE);
    n->data = value;
    n->next = NULL;
    return n;
}

Node* insertEnd(Node *head, int value) {
    Node *n = createNode(value);
    if (!head) return n;

    Node *cur = head;
    while (cur->next) cur = cur->next;
    cur->next = n;
    return head;
}

void display(Node *head) {
    while (head) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// Q21. Find middle node (second middle for even length)
Node* findMiddle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Q22. Reverse iteratively
Node* reverseIterative(Node *head) {
    Node *prev = NULL, *cur = head;

    while (cur) {
        Node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

// Q23. Reverse recursively
Node* reverseRecursive(Node *head) {
    if (!head || !head->next) return head;

    Node *newHead = reverseRecursive(head->next);
    head->next->next = head;
    head->next = NULL;
    return newHead;
}

// Q24. Detect cycle using Floyd's algorithm
int hasCycle(Node *head) {
    Node *slow = head, *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

// Q25. Find the starting node of a cycle
Node* cycleStart(Node *head) {
    Node *slow = head, *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return NULL;
}

void freeList(Node *head) {
    while (head) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void) {
    Node *head = NULL;
    for (int i = 10; i <= 50; i += 10)
        head = insertEnd(head, i);

    printf("Original: ");
    display(head);

    Node *mid = findMiddle(head);
    printf("Q21 Middle: %d\n", mid ? mid->data : -1);

    Node *reversed = reverseIterative(head);
    printf("Q22 Reversed iteratively: ");
    display(reversed);

    head = reverseRecursive(reversed);
    printf("Q23 Reversed recursively: ");
    display(head);

    // Q24 and Q25: create a cycle from the last node to node 30.
    Node *third = head->next->next;
    Node *last = head;
    while (last->next) last = last->next;
    last->next = third;

    printf("Q24 Has cycle: %s\n",
           hasCycle(head) ? "Yes" : "No");

    Node *start = cycleStart(head);
    printf("Q25 Cycle starts at: %d\n",
           start ? start->data : -1);

    // Break the cycle before freeing the list.
    last->next = NULL;
    freeList(head);
    return 0;
}

C++

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int value) : data(value), next(nullptr) {}
};

Node* insertEnd(Node* head, int value) {
    Node* n = new Node(value);
    if (!head) return n;

    Node* cur = head;
    while (cur->next) cur = cur->next;
    cur->next = n;
    return head;
}

void display(Node* head) {
    while (head) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << "NULL\n";
}

// Q21
Node* findMiddle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Q22
Node* reverseIterative(Node* head) {
    Node *prev = nullptr, *cur = head;

    while (cur) {
        Node* next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

// Q23
Node* reverseRecursive(Node* head) {
    if (!head || !head->next) return head;

    Node* newHead = reverseRecursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

// Q24
bool hasCycle(Node* head) {
    Node *slow = head, *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

// Q25
Node* cycleStart(Node* head) {
    Node *slow = head, *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

void freeList(Node* head) {
    while (head) {
        Node* next = head->next;
        delete head;
        head = next;
    }
}

int main() {
    Node* head = nullptr;
    for (int i = 10; i <= 50; i += 10)
        head = insertEnd(head, i);

    cout << "Original: ";
    display(head);

    cout << "Q21 Middle: " << findMiddle(head)->data << '\n';

    Node* reversed = reverseIterative(head);
    cout << "Q22 Reversed iteratively: ";
    display(reversed);

    head = reverseRecursive(reversed);
    cout << "Q23 Reversed recursively: ";
    display(head);

    Node* third = head->next->next;
    Node* last = head;
    while (last->next) last = last->next;
    last->next = third;

    cout << "Q24 Has cycle: "
         << (hasCycle(head) ? "Yes" : "No") << '\n';

    Node* start = cycleStart(head);
    cout << "Q25 Cycle starts at: "
         << (start ? start->data : -1) << '\n';

    last->next = nullptr;
    freeList(head);
    return 0;
}

Java

public class LinkedList21To25 {

    static class Node {
        int data;
        Node next;

        Node(int value) {
            data = value;
        }
    }

    static Node insertEnd(Node head, int value) {
        Node n = new Node(value);
        if (head == null) return n;

        Node cur = head;
        while (cur.next != null) cur = cur.next;
        cur.next = n;
        return head;
    }

    static void display(Node head) {
        while (head != null) {
            System.out.print(head.data + " -> ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    // Q21
    static Node findMiddle(Node head) {
        Node slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // Q22
    static Node reverseIterative(Node head) {
        Node prev = null, cur = head;

        while (cur != null) {
            Node next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }

    // Q23
    static Node reverseRecursive(Node head) {
        if (head == null || head.next == null) return head;

        Node newHead = reverseRecursive(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    // Q24
    static boolean hasCycle(Node head) {
        Node slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    // Q25
    static Node cycleStart(Node head) {
        Node slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        Node head = null;
        for (int i = 10; i <= 50; i += 10)
            head = insertEnd(head, i);

        System.out.print("Original: ");
        display(head);

        System.out.println("Q21 Middle: " + findMiddle(head).data);

        Node reversed = reverseIterative(head);
        System.out.print("Q22 Reversed iteratively: ");
        display(reversed);

        head = reverseRecursive(reversed);
        System.out.print("Q23 Reversed recursively: ");
        display(head);

        Node third = head.next.next;
        Node last = head;
        while (last.next != null) last = last.next;
        last.next = third;

        System.out.println("Q24 Has cycle: " +
                           (hasCycle(head) ? "Yes" : "No"));

        Node start = cycleStart(head);
        System.out.println("Q25 Cycle starts at: " +
                           (start == null ? -1 : start.data));

        // Break cycle so the list can be traversed safely afterward.
        last.next = null;
    }
}

Solution and explanation

Solution

Detect the cycle with Floyd's slow/fast pointers. Then find the node just before the cycle start and set its next to NULL.

Step by step

1. Move slow one step and fast two steps until they meet (no meeting → no cycle, nothing to do).
2. Reset slow = head.
3. Special case: if the meeting point is the head (the whole list is a loop), walk fast around until fast->next == head, then cut.
4. Otherwise advance slow and fast one step at a time until slow->next == fast->next; that shared next node is the cycle start, so fast is the last node of the loop. Set fast->next = NULL.

Example

10 → 20 → 30 → 40 → 50 → back to 30 becomes 10 → 20 → 30 → 40 → 50 → NULL.

Complexity

• O(n) time, O(1) space.

Solution and explanation

Solution

Two pointers with a gap of n: move first n steps ahead, then move both until first is NULL. second is then the nth node from the end. One pass, no length needed.

Dry run (n = 2 on 10 → 20 → 30 → 40 → 50)

Edge cases

• n <= 0 or n longer than the list → return NULL.

Complexity

• O(n) time, O(1) space.

Solution and explanation

Solution

Use a dummy head and a tail pointer. Repeatedly attach the smaller front node of the two lists; when one list ends, attach the rest of the other. No new nodes are created.

Dry run

1 → 3 → 5 and 2 → 4 → 6 → take 1, 2, 3, 4, 5, then attach 6 → 1 → 2 → 3 → 4 → 5 → 6.

Complexity

• O(n + m) time, O(1) extra space. Using <= keeps equal values in their original order (stable merge).

Solution and explanation

Solution

In a sorted list duplicates are adjacent. Compare each node with its next: if equal, unlink (and free) the next node; otherwise move forward.

Dry run

1 → 1 → 2 → 3 → 3 → 3 → 4 → 1 → 2 → 3 → 4.

Note

For an unsorted list use a hash set of seen values (O(n) time, O(n) space).

Complexity

• O(n) time, O(1) space.

Solution and explanation

Solution

Find the middle, reverse the second half, compare the two halves node by node, then reverse the second half back so the original list is unchanged.

Step by step

1. Slow/fast pointers: stop when fast->next or fast->next->next is NULL; slow is the end of the first half.
2. Reverse the list after slow.
3. Compare from head and from the reversed half; any mismatch → not a palindrome.
4. Reverse the second half again and reattach it to slow->next.

Example

1 → 2 → 3 → 2 → 1 → Yes.

Complexity

• O(n) time, O(1) space (a stack-based version needs O(n) space).

Solution and explanation

Solution

Two pointers walk both lists; when one reaches the end it continues from the head of the other list. Both travel lenA + lenB nodes, so they meet at the first shared node, or both become NULL together when the lists do not intersect.

Note: intersection means the same node in memory (pointer identity), not equal values.

Example

A: 3 → 6 → 8 → 10, B: 4 → 8 → 10, where 8 and 10 are the same nodes → intersection at 8.

Complexity

• O(m + n) time, O(1) space.

Solution and explanation

Solution

Digits are stored in reverse order (units first). Add digit by digit with a carry, creating a new node for each digit of the sum; keep going while either list has digits or a carry remains.

Dry run

2 → 4 → 3 (342) + 5 → 6 → 4 (465):

Result 7 → 0 → 8 (807).

Complexity

• O(max(m, n)) time; O(max(m, n)) space for the result.

Solution and explanation

Solution

Merge sort suits linked lists: splitting needs no random access and merging needs no extra array.

Step by step

1. Base case: empty or single node.
2. Find the middle with slow/fast pointers (fast starts at head->next so the left half is never empty) and cut the list in two.
3. Sort each half recursively.
4. Merge the two sorted halves (Q28).

Example

4 → 2 → 1 → 3 → 1 → 2 → 3 → 4.

Complexity

• O(n log n) time; O(log n) recursion stack.