DEV Community: Shivam Tyagi

How to find intersection of two singly linked lists in a simple and optimal way in java

Shivam Tyagi — Tue, 13 Aug 2024 10:34:29 +0000

To find the intersection of two singly linked lists in a simple and optimal way, you can use the following approach. The key idea is to align the ends of both linked lists by adjusting the start point of the longer list, and then traverse both lists simultaneously to find the intersection point.

Steps:

Calculate Lengths: First, calculate the lengths of both linked lists.
Align Start Pointers: If one list is longer than the other, advance its pointer to align the lengths of both lists.
Find Intersection: Traverse both lists simultaneously. The first node where they meet is the intersection point.

Java Implementation:

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {

    // Function to get the intersection node of two linked lists
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        // Calculate the lengths of both linked lists
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);

        // Align the start of both lists
        while (lengthA > lengthB) {
            headA = headA.next;
            lengthA--;
        }

        while (lengthB > lengthA) {
            headB = headB.next;
            lengthB--;
        }

        // Traverse both lists together to find the intersection
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }

        return headA;  // or headB, they are the same at intersection point
    }

    // Utility function to calculate the length of a linked list
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create two linked lists
        // List A: 1 -> 3 -> 5 -> 7 -> 9 -> 11
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(3);
        headA.next.next = new ListNode(5);
        headA.next.next.next = new ListNode(7);
        headA.next.next.next.next = new ListNode(9);
        headA.next.next.next.next.next = new ListNode(11);

        // List B: 2 -> 4 -> 9 -> 11
        ListNode headB = new ListNode(2);
        headB.next = new ListNode(4);
        headB.next.next = headA.next.next.next.next;  // 9
        headB.next.next.next = headA.next.next.next.next.next;  // 11

        System.out.println("List A:");
        list.printList(headA);

        System.out.println("List B:");
        list.printList(headB);

        // Find intersection
        ListNode intersection = list.getIntersectionNode(headA, headB);

        if (intersection != null) {
            System.out.println("Intersection at node with value: " + intersection.val);
        } else {
            System.out.println("No intersection.");
        }
    }
}

Explanation:

ListNode Class:
- Represents each node in the linked list with a value (val) and a pointer to the next node (next).
getIntersectionNode Method:
- Calculate Lengths: The lengths of both linked lists are calculated using the getLength method.
- Align Start Pointers: If the lists have different lengths, the longer list's pointer is advanced to align with the shorter list's pointer.
- Traverse Together: Both pointers are then moved simultaneously. The first node where they match is the intersection node.
getLength Method:
- A helper method to calculate the length of a linked list.
printList Method:
- A utility function to print the nodes of the linked list.
main Method:
- Create two linked lists: For example, 1 -> 3 -> 5 -> 7 -> 9 -> 11 and 2 -> 4 -> 9 -> 11, where the intersection starts at node 9.
- Find and print the intersection: The program will output 9 as the intersection point.

Complexity:

Time Complexity: ( O(m + n) ), where ( m ) and ( n ) are the lengths of the two linked lists. The lists are traversed a maximum of twice.
Space Complexity: ( O(1) ), since only a few extra pointers are used.

This method is simple and optimal, ensuring that you find the intersection point of two singly linked lists in an efficient manner.

Merge two sorted linked lists in java simple and optimal way

Shivam Tyagi — Mon, 12 Aug 2024 12:05:26 +0000

Merging two sorted linked lists is a common problem that can be solved efficiently. Here's how you can do it in a simple and optimal way using Java.

Steps:

Create a Dummy Node: Use a dummy node to help simplify the merge process. This node will serve as the start of the merged list.
Compare Nodes: Compare the current nodes of both linked lists. Attach the smaller node to the merged list and move the pointer of that list forward.
Handle Remaining Nodes: If one list is exhausted before the other, attach the remaining nodes of the non-exhausted list to the merged list.
Return the Merged List: The merged list starts from the node next to the dummy node.

Java Implementation:

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {

    // Function to merge two sorted linked lists
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Create a dummy node to act as the starting point
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Traverse both lists and compare nodes
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // If one list is exhausted, link the remaining nodes of the other list
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        // The merged list starts from the next node of the dummy node
        return dummy.next;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create first sorted linked list: 1 -> 3 -> 5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        // Create second sorted linked list: 2 -> 4 -> 6
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        System.out.println("First List:");
        list.printList(l1);

        System.out.println("Second List:");
        list.printList(l2);

        // Merge the two lists
        ListNode mergedList = list.mergeTwoLists(l1, l2);

        System.out.println("Merged List:");
        list.printList(mergedList);
    }
}

Explanation:

ListNode Class:
- Represents each node in the linked list with an integer value (val) and a pointer to the next node (next).
mergeTwoLists Method:
- Dummy Node: A dummy node (dummy) is used to simplify the merging process by providing a starting point.
- Comparison Loop: We traverse both linked lists, comparing the current nodes. The smaller node is added to the merged list, and we move to the next node in that list.
- Remaining Nodes: After one of the lists is exhausted, we attach the remaining part of the other list directly to the merged list.
- Return: Finally, the merged list starts from the node next to the dummy node.
printList Method:
- This utility function prints all the nodes in the linked list for easy visualization.
main Method:
- Create two sorted linked lists: For example, 1 -> 3 -> 5 and 2 -> 4 -> 6.
- Merge the lists: The merged list will be 1 -> 2 -> 3 -> 4 -> 5 -> 6.
- Print the lists: Before and after merging to see the effect.

Complexity:

Time Complexity: ( O(n + m) ), where ( n ) and ( m ) are the lengths of the two linked lists. Each node in both lists is processed exactly once.
Space Complexity: ( O(1) ), as no additional space is used apart from a few pointers.

This method is both simple and optimal for merging two sorted linked lists, ensuring efficient and clean code.

Uses of @spy annotation in junit testing

Shivam Tyagi — Mon, 12 Aug 2024 08:22:12 +0000

The @Spy annotation in JUnit, particularly when used with Mockito, is applied to create a spy on an actual object. A spy is a partial mock, which means that you can mock some methods of the object while retaining the real behavior of other methods.

Here are some common uses of the @Spy annotation:

Partial Mocking:

If you have an object where most methods need to retain their actual behavior but one or two methods need to be mocked, you can use a spy.
Example:

 @Spy
 private List<String> spyList = new ArrayList<>();

 @Test
 public void testSpy() {
     spyList.add("Mockito");
     Mockito.verify(spyList).add("Mockito");
     assertEquals(1, spyList.size());

     Mockito.doReturn(100).when(spyList).size();
     assertEquals(100, spyList.size());
 }

Overriding Real Method Behavior:

You can use a spy to override specific method behavior of a real object while keeping the rest of the methods intact.
Example:

 @Spy
 private MyClass myClass = new MyClass();

 @Test
 public void testSpyWithMethodOverride() {
     Mockito.doReturn("Mocked Value").when(myClass).someMethod();
     assertEquals("Mocked Value", myClass.someMethod());
 }

Verifying Method Calls:

You can verify if certain methods were called on the spy, which is helpful when testing interactions.
Example:

 @Spy
 private MyClass myClass = new MyClass();

 @Test
 public void testMethodCallVerification() {
     myClass.someMethod();
     Mockito.verify(myClass).someMethod();
 }

Combining with @InjectMocks:

@Spy can be used in conjunction with @InjectMocks to inject spied objects into the object being tested, allowing partial mocking within the tested class.
Example:

 @Spy
 private MyDependency dependency;

 @InjectMocks
 private MyService service;

 @Test
 public void testService() {
     Mockito.doReturn("Mocked Result").when(dependency).doSomething();
     assertEquals("Mocked Result", service.performAction());
 }

Testing Legacy Code:
- When dealing with legacy code that you cannot easily refactor, using a spy allows you to isolate and mock specific methods without changing the original code.

In summary, the @Spy annotation is useful when you need to control or verify specific behaviors of an actual object while keeping the rest of the object's behavior unchanged.

How to reverse a linked list in simple and optimal way in java

Shivam Tyagi — Mon, 12 Aug 2024 07:55:32 +0000

To reverse a linked list in Java, you can use an iterative approach which is both simple and optimal in terms of time complexity O(n) and space complexity O(1). Here’s how you can do it:

Iterative Approach:

Initialize three pointers: previous, current, and next.
Traverse through the list, reversing the direction of the next pointer for each node.

Here’s a step-by-step implementation:
`class ListNode {
int val;
ListNode next;

ListNode(int val) {
    this.val = val;
    this.next = null;
}

}

public class LinkedList {

// Function to reverse the linked list
public ListNode reverseList(ListNode head) {
    ListNode previous = null;
    ListNode current = head;
    ListNode next = null;

    while (current != null) {
        next = current.next;  // Store the next node
        current.next = previous;  // Reverse the current node's pointer
        previous = current;  // Move the previous pointer one step forward
        current = next;  // Move the current pointer one step forward
    }

    return previous;  // Previous will be the new head
}

// Function to print the linked list
public void printList(ListNode head) {
    ListNode temp = head;
    while (temp != null) {
        System.out.print(temp.val + " ");
        temp = temp.next;
    }
    System.out.println();
}

public static void main(String[] args) {
    LinkedList list = new LinkedList();

    // Creating the linked list: 1 -> 2 -> 3 -> 4 -> 5
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);

    System.out.println("Original List:");
    list.printList(head);

    head = list.reverseList(head);

    System.out.println("Reversed List:");
    list.printList(head);
}

Explanation:

ListNode Class:

Represents a node in the linked list with an integer value and a pointer to the next node.

reverseList Method:

previous: Keeps track of the previous node (starts as null).
current: Keeps track of the current node (starts as head).
next: Temporarily stores the next node.
The while loop runs until current becomes null.
Inside the loop:
next stores the next node.
The next pointer of the current node is reversed to point to previous.
Move previous and current one step forward

This approach effectively reverses the linked list in linear time with constant space complexity.

✨ Enjoyed this post? If you found this content valuable, don’t forget to like to show your support! Your claps help others discover these insights.

🔔 Want to stay updated? Hit that follow button to never miss out on my latest posts and updates. Join our community and be part of the conversation!

Thanks for your support and engagement! 🙌