Linked List Tips

Linked List is a fairly popular data structure. And the tasks associated with this structure can often be found at an interview. In this article, we will break down everyday Linked List tasks.

A Linked List is a linked list where one item refers to another.

One of the most common techniques for solving Linked List problems is the two sliders technique. We create a fast and slow slider and move the slow one forward, one non-zero. And fast (for example) by two.

Task. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false

How can we know if there is a loop? If you create two sliders, when the slow one enters the loop, the fast one will catch up with it by 1. And it turns out they will meet. And if there is no loop, then the fast slider will be null. I hope the idea is clear. Let's take a look at the code:

` public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
} else {
ListNode slow = head;
ListNode fast = head;

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

            if (slow == fast){
                return true;
            }
        }
    }
    return false;
}

`

How do we find the node where the loop starts? It is not hard to see from the previous algorithm that the fast slider will reach the slow one in N steps. Since our loop may not start from the beginning of the sheet, when the slow slider approaches the beginning of the loop after X steps, the fast slider will go X * 2. And the fast one will be at a distance of N - 2 * X steps. On the other hand, the fast catches up with the slow one by 1 every step. It turns out that the fast lags behind the slow one by N - 2X. Catching up each time by 1, the fast and slow runners will meet at point N - X. This means that we can move any slider to the beginning of the sheet and move the runners step by step from the meeting point and the head. The place where they meet will be the beginning of the loop. If you still have questions about the algorithm, write. I will be happy to answer.
Let's take a look at the code:

`public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;

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

        if (slow == fast){
            break;
        }
    }

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

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

Oh, I really like the next challenge. The intersection of Two Linked Lists.

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

How do we find these intersections? What if the length of the sheets is different? What if they don't intersect at all?

I suggest that you first check if the sheets overlap.
We just go through one and the second sheet and see that the resulting baud is the same.
What to do next?
During the first pass through the sheets, we can calculate the length of each of them. We get the missing number of nodes by subtracting the smaller size from the larger. With this amount, you can move along the sheet. And then, we can begin to run on two sheets and look for the place of their intersection. Cool, isn't it?

`public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode aEnd = headA;
ListNode bEnd = headB;
int aLength = 1;
int bLength = 1;

    while (aEnd != null){
        aEnd = aEnd.next;
        aLength++;
    }

    while (bEnd != null){
        bEnd = bEnd.next;
        bLength++;
    }

    if (aEnd != bEnd) {
        return null;
    }

    aEnd = headA;
    bEnd = headB;
    int shift = 0;
    if (aLength > bLength) {
        shift = aLength - bLength;
        while (shift > 0){
            aEnd = aEnd.next;
            shift --;
        }
    } else if (bLength > aLength) {
        shift = bLength - aLength;
        while (shift > 0){
            bEnd = bEnd.next;
            shift --;
        }
    }

    while(aEnd != null) {
        if (aEnd == bEnd){
            return aEnd;
        }
        aEnd = aEnd.next;
        bEnd = bEnd.next;
    }

    return null;
} `

By the way, have you ever wondered how you can remove a specific node from the end of the List? After all, we only have one direction? How to delete?
Fast and slow runners come to our rescue again. Move the fast slider by the required number of elements.
Next, connect the slow slider and run until the fast slider becomes NULL. When fast is NULL, the slow slider is in front of the element to be removed. And that's all. Then we can simply rearrange the links, and the required part is removed.

`public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode empty = new ListNode();

    empty.next = head;
    ListNode slow = empty;
    ListNode fast = empty;

    for (int i = 0; i < n && fast != null; i++){
        fast = fast.next;
    }

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

    slow.next = slow.next.next;
    return empty.next;
}

`

Let's summarize. When using the slider technique, always test the next element for NULL. It is necessary to correctly determine the conditions for ending the loop. Run different options to make sure your requirements are correct.