traversing singly linked list in Java

Question

I have a simple Java question. As shown in the below code:

public static ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode start = new ListNode(0);
        ListNode slow = start, fast = start;
        slow.next = head;

        //Move fast in front so that the gap between slow and fast becomes n
        for(int i=1; i<=n+1; i++)   {
            fast = fast.next;
        }
        //Move fast to the end, maintaining the gap
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        //Skip the desired node
        slow.next = slow.next.next;
        return start.next;
    }

Start, fast and slow address the same object. I don't get why "slow = slow.next;" will not change the start object, but "slow.next = slow.next.next;" will change the start object.

Your question title doesn't really relate to what you're doing. I made the incorrect assumption that you were just trying to visit each node. Could you maybe improve it? — byxor
– byxor, Commented Dec 11, 2016 at 14:35
This also seems to scream for null pointer exceptions. You create a start node; which probably means that it hasn't any followers in that list. Iterating that sounds like asking for trouble. — GhostCat
– GhostCat, Commented Dec 11, 2016 at 14:36
@GhostCat except that two lines down, there's slow.next = head; As one line above you have slow=fast=start, the slow.next=head means 'start is initialized with the meaning of node at index -1 and slow/fast are set to this position'. Then everything is fine and dandy if the list contains N elements because the for(int i=1; i<=n+1; i++) cycle doesn't test against null. — Adrian Colomitchi
– Adrian Colomitchi, Commented Dec 11, 2016 at 14:47

Eran · Accepted Answer · 2016-12-11 14:34:24Z

2

slow is a local variable, so changing its value to refer to a new instance of ListNode doesn't affect the original list.

However, if slow refers to a ListNode that belongs to your list, changing slow.next to refer to a new instance changes the state of your list.

It may be clearer if you use a setter to modify the next node :

slow.next = slow.next.next;

would be equivalent to :

slow.setNext(slow.next.next);

So if slow refers to a ListNode that belongs to your list, changing its state is changing the state of your list.

answered Dec 11, 2016 at 14:34

Eran

395k57 gold badges726 silver badges793 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

traversing singly linked list in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related