LINKED LISTS

Reverse Linked List

public class Solution {
    public ListNode reverseList(ListNode A) {
        ListNode prev=null;
        ListNode curr=A;
        ListNode next=null;
        
        while(curr!=null){
            next=curr.next;
            curr.next=prev;
            prev=curr;
            curr=next;
        }
       return prev; 
    }
}

Intersection of Linked Lists

public class Solution {
public ListNode getIntersectionNode(ListNode a, ListNode b) {
if(a==null || b==null){
return null;
}

ListNode pa=a, pb=b;
while(pa!=pb){
pa = pa == null ? b : pa.next;
pb = pb == null ? a : pb.next;
}
return pa;
}
}

Sort Binary Linked List

public class Solution {
    public ListNode solve(ListNode A) {
        int count0=0, count1=0;
        ListNode curr=A;
        
        while(curr!=null){
            if(curr.val==0){
                count0++;
            }else{
                count1++;
            }
            curr=curr.next;
        }
        curr=A;
        while(count0>0){
            curr.val=0;
            curr=curr.next;
            count0--;
        }
        while(count1>0){
            curr.val=1;
            curr=curr.next;
            count1--;
        }
       return A; 
    }
}

Partition List
public class Solution {
    public ListNode partition(ListNode A, int B) {
        ListNode lessHead=new ListNode(0);
        ListNode lessTail=lessHead;
        ListNode greaterOrEqualHead=new ListNode(0);
        ListNode greaterOrEqualTail=greaterOrEqualHead;
        
        while(A!=null){
            if(A.val<B){
                lessTail.next=A;
                lessTail=lessTail.next;
            }else{
                greaterOrEqualTail.next=A;
                greaterOrEqualTail=greaterOrEqualTail.next;
            }
            A=A.next;
        }
        greaterOrEqualTail.next=null;
            lessTail.next=greaterOrEqualHead.next;
            return lessHead.next;
        }
    }

Insertion Sort List
public class Solution {
    public ListNode insertionSortList(ListNode A) {
        
        if(A==null||A.next==null){
            return A;
        }
        ListNode sortedList=null;
        
        while(A!=null){
            ListNode current=A;
            A=A.next;
        
        if(sortedList==null||current.val<sortedList.val){
            current.next=sortedList;
            sortedList=current;
            }else{
            ListNode runner=sortedList;
            while(runner.next!=null && current.val>runner.next.val){
                runner=runner.next;
            }
            current.next=runner.next;
            runner.next=current;
            }
        }
        return sortedList;
    }
}


Sort List
public class Solution {
    public ListNode sortList(ListNode A) {
        
        if(A==null||A.next==null){
            return A;
        }
        ListNode slow=A;
        ListNode fast=A.next;
        
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode middle=slow.next;
        slow.next=null;
        
        ListNode left=sortList(A);
        ListNode right=sortList(middle);
        
        ListNode dummy=new ListNode(0);
        ListNode curr=dummy;
        
        while(left!=null && right!=null){
            if(left.val<right.val){
            curr.next=left;
            left=left.next;
        }else{
            curr.next=right;
            right=right.next;
        }
        curr=curr.next;
        }
        if(left!=null){
            curr.next=left;
        }else{
            curr.next=right;
        }
        return dummy.next;
    }
}


Palindrome List
public class Solution {
    public int lPalin(ListNode A) {
        ArrayList<Integer> values=new ArrayList<>();
        ListNode current=A;
        
        while(current!=null){
            values.add(current.val);
            current=current.next;
        }
        int left=0;
        int right=values.size()-1;
        
        while(left<right){
            if(!values.get(left).equals(values.get(right))){
                return 0;
            }
            left++;
            right--;
        }
        return 1;
    }
}

Remove Duplicates from Sorted List II
public class Solution {
    public ListNode deleteDuplicates(ListNode A) {
        
    if (A == null || A.next == null) {
        return A;
    }
    
    ListNode dummy = new ListNode(0);
    dummy.next = A;
    ListNode prev = dummy;
    ListNode curr = A;
    
    while (curr != null) {
        boolean isDup = false;
        while (curr.next != null && curr.val == curr.next.val) {
            curr = curr.next;
            isDup = true;
        }
        if (isDup) {
            prev.next = curr.next;
        } else {
            prev = curr;
        }
        curr = curr.next;
    }
    
    return dummy.next;


    }
}

Remove Duplicates from Sorted Listpublic class Solution {
    public ListNode deleteDuplicates(ListNode A) {
        
    if (A == null) {
        return null;
    }
    ListNode current = A;
    ListNode previous = null;
    while (current != null) {
        if (previous != null && current.val == previous.val) {
            previous.next = current.next;
        } else {
            previous = current;
        }
        current = current.next;
    }
    return A;


    }
}


Merge Two Sorted Lists
public class Solution {
    public ListNode mergeTwoLists(ListNode A, ListNode B) {
        
        ListNode dummy=new ListNode(0);
        ListNode current=dummy;
        
        while(A!=null && B!=null){
            if(A.val<=B.val){
                current.next=A;
                A=A.next;
            }else{
                current.next=B;
                B=B.next;
            }
            current=current.next;
        }
            if(A!=null){
                current.next=A;
            }else{
                current.next=B;
            }
        
        return dummy.next;
    }
}

Remove Nth Node from List Endpublic class Solution {
    public ListNode removeNthFromEnd(ListNode A, int B) {
        
        ListNode dummy = new ListNode(0);
    dummy.next = A;

    ListNode slow = dummy;
    ListNode fast = dummy;

    // Move the fast pointer B+1 steps ahead
    for (int i = 0; i <= B; i++) {
        if (fast == null) {
            // B is greater than the size of the list,
            // so remove the first node (dummy.next)
            return dummy.next.next;
        }
        fast = fast.next;
    }

    // Move both pointers until the fast pointer reaches the end
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }

    // Remove the B-th node from the end
    slow.next = slow.next.next;

    return dummy.next;
    }
}


K reverse linked list
public class Solution {
    public ListNode reverseList(ListNode A, int B) {
        
        ListNode current = A;
    ListNode previous = null;
    ListNode next = null;
    int count = 0;
    
    // Reverse the links for each group of size K
    while (count < B && current != null) {
        next = current.next;
        current.next = previous;
        previous = current;
        current = next;
        count++;
    }
    
    // If there are remaining nodes, recursively reverse them
    if (next != null) {
        A.next = reverseList(next, B);
    }
    
    return previous;
    }
}


Swap List Nodes in pairs
public class Solution {
    public ListNode swapPairs(ListNode A) {
        
    
    // Base case: If the list is empty or has only one node, no swaps are needed
    if (A == null || A.next == null) {
        return A;
    }

    // Create a dummy node to serve as the new head of the modified list
    ListNode dummy = new ListNode(0);
    dummy.next = A;

    // Initialize the current and previous pointers
    ListNode prev = dummy;
    ListNode curr = A;

    // Iterate through the list and swap pairs of adjacent nodes
    while (curr != null && curr.next != null) {
        // Nodes to be swapped
        ListNode first = curr;
        ListNode second = curr.next;

        // Swapping the nodes
        prev.next = second;
        first.next = second.next;
        second.next = first;

        // Move the pointers for the next iteration
        prev = first;
        curr = first.next;
    }

    // Return the head of the modified list
    return dummy.next;


    }
}

Reverse Alternate K Nodespublic class Solution {
    public ListNode solve(ListNode A, int B) {
        
        if (A == null || B <= 1) {
        return A;
    }
    
    ListNode prev = null;
    ListNode curr = A;
    ListNode next = null;
    int count = 0;
    
    // Reverse the first B nodes
    while (curr != null && count < B) {
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
        count++;
    }
    
    // Connect the first reversed group to the next group
    if (next != null) {
        A.next = next;
    }
    
    // Skip the next B nodes
    count = 0;
    while (count < B - 1 && curr != null) {
        curr = curr.next;
        count++;
    }
    
    // Recursively reverse the remaining groups
    if (curr != null) {
        curr.next = solve(curr.next, B);
    }
    
    return prev;

    }
}

List Cycle
public class Solution {
    public ListNode detectCycle(ListNode a) {
        ListNode slow = a;
    ListNode fast = a;

    // Step 1: Find the meeting point of the slow and fast pointers
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            break;
        }
    }

    // Step 2: Check if there is no cycle in the list
    if (fast == null || fast.next == null) {
        return null;
    }

    // Step 3: Reset the slow pointer to the head of the list
    slow = a;

    // Step 4: Move both pointers one step at a time until they meet again
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }

    // Step 5: Return the meeting point as the result
    return slow;

    }
}

Add Two Numbers as Lists
public class Solution {
    public ListNode addTwoNumbers(ListNode A, ListNode B) {
        
        ListNode dummy = new ListNode(0); // Dummy node to hold the result
    ListNode current = dummy; // Pointer to the current node in the result list
    int carry = 0; // Variable to hold the carry value

    while (A != null || B != null || carry != 0) {
        int sum = carry;

        // Add the values of the current nodes in A and B (if available)
        if (A != null) {
            sum += A.val;
            A = A.next;
        }
        if (B != null) {
            sum += B.val;
            B = B.next;
        }

        // Create a new node with the sum % 10 and update the carry value
        current.next = new ListNode(sum % 10);
        current = current.next;
        carry = sum / 10;
    }

    return dummy.next; // Return the result list (excluding the dummy node)

    }
}

Search This Blog

yogu

Reverse Linked List

Intersection of Linked Lists

public class Solution {
public ListNode getIntersectionNode(ListNode a, ListNode b) {
if(a==null || b==null){
return null;
}

ListNode pa=a, pb=b;
while(pa!=pb){
pa = pa == null ? b : pa.next;
pb = pb == null ? a : pb.next;
}
return pa;
}
}

Sort Binary Linked List

Partition List

Insertion Sort List

Sort List

Palindrome List

Remove Duplicates from Sorted List II

Remove Duplicates from Sorted List

Merge Two Sorted Lists

Remove Nth Node from List End

K reverse linked list

Swap List Nodes in pairs

Reverse Alternate K Nodes

List Cycle

Add Two Numbers as Lists

Linked Lists

Comments