CODEWITHSUNDEEP
javalinked-listsingly-linked-list
ilovestackoverflow
ilovestackoverflow

Reputation: 1

Effect to pointers after reversing a Linked List

In the following code with a stringy Linked List, I created 2 pointers, fast and slow. I move fast pointer to the end and slow pointer to the middle. I then reversed the right half.

public void test(ListNode head) {
    ListNode fast = head, slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;  //to the end of the list
        slow = slow.next;   //to the middle
    }
    slow = reverse(slow);  
    fast = head;   
    while (fast != null) {
        System.out.println(fast.val); //fast pointer only goes until the middle of the list
        fast=fast.next;
    }
    return true;
}
public ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

What I don't understand is that as soon as I reversed the right half, fast pointer only has access to elements until the middle of the LinkedList.

For example, let's say the LinkedList has 1->2->4->8->5. After reverse(slow), the slow pointer points to 5->8->4, which is good. However, now the fast pointer points to 1->2->4, which I don't understand why. Why doesn't it have access to 8 and 5? What did the reverse method do to the fast pointer?

Upvotes: 0

Views: 232

Answers (1)

Deepak Patankar
Deepak Patankar

Reputation: 3272

Your Final linked list is 1->2->4<-8<-5 and 4->(null). You should set the next of 2 to 2->5 somewhere which will solve the problem.

Upvotes: 3

Related Questions