Reversing a singly linked list iteratively

Question

Has to be O(n) and in-place (space complexity of 1). The code below does work, but is there a simpler or better way?

public void invert() {
    if (this.getHead() == null)
        return;
    if (this.getHead().getNext() == null)
        return;
    //this method should reverse the order of this linked list in O(n) time
    Node<E> prevNode = this.getHead().getNext();
    Node<E> nextNode = this.getHead().getNext().getNext();
    prevNode.setNext(this.getHead());
    this.getHead().setNext(nextNode);
    nextNode = nextNode.getNext();

    while (this.getHead().getNext() != null)
    {
        this.getHead().getNext().setNext(prevNode);
        prevNode = this.getHead().getNext();
        this.getHead().setNext(nextNode);
        if (nextNode != null)
            nextNode = nextNode.getNext();
    }
    this.head = prevNode;
}

RonJRH · Accepted Answer · 2012-10-17T22:54:57.647

10

Edited to remove the extra comparison per iteration:

    public void invert() {
        Node<E> prev = null, next = null;;
        if (head == null) return;
        while (true) {
            next = head.getNext();
            head.setNext(prev);
            prev = head;
            if (next == null) return;
            head = next;
        }
    }

edited Oct 17 '12 at 22:54

answered Oct 17 '12 at 22:11

RonJRH

129
6

Handles head node being null, and generalizes all other cases. – RonJRH Oct 17 '12 at 23:03
Is the second `;` on Ln 2 of any significance? – Carcigenicate Nov 26 '14 at 22:10

score 1 · Answer 2 · edited May 23 '17 at 10:29

1

Works with this implementation of LinkedList: https://stackoverflow.com/a/25311/234307

public void reverse() {

    Link previous = first;
    Link currentLink = first.nextLink;
    first.nextLink = null;

    while(currentLink != null) {        

        Link realNextLink = currentLink.nextLink;
        currentLink.nextLink = previous;                        
        previous = currentLink; 
        first = currentLink;    
        currentLink = realNextLink;

    }

}

edited May 23 '17 at 10:29

Community

1
1

answered Oct 17 '12 at 22:02

jn1kk

5,012
2
45
72

You don't actually need to maintain `first` at each iteration, right? If the intent is to return a pointer to the head of the reversed list, you could simply return `previous` at the very end. – yangmillstheory Sep 16 '15 at 05:53

score 0 · Answer 3 · answered Oct 17 '12 at 21:43

How about this:

public void invert() {
    if (head != null) {
        for (Node<E> tail = head.getNext(); tail != null; ) {
            Node<E> nextTail = tail.getNext();
            tail.setNext(head);
            head = tail;
            tail = nextTail;
        }
    }
}

score 0 · Answer 4 · answered Oct 17 '12 at 22:08

Using a self-contained implementation, i.e. the List is represented by the head Node:

public class Node<E>
{
    Node<E> next;
    E value;

    public Node(E value, Node<E> next)
    {
        this.value = value;
        this.next = next;
    }

    public Node<E> reverse()
    {
        Node<E> head = null;
        Node<E> current = this;
        while (current != null) {
            Node<E> save = current;
            current = current.next;
            save.next = head;
            head = save;
        }
        return head;
    }
}

score 0 · Answer 5 · answered Jan 16 '13 at 06:01

public void reverse(){

    Node middle = head;
    Node last = head;
    Node first = null;

    while(last != null){

        middle = last;
        last = last.next;
        middle.next = first;
        first = middle;
    }

    head = middle;
}

score 0 · Answer 6 · answered Oct 05 '13 at 16:59

0

public void invert() {  
  if (first == null) return;  
  Node<E> prev = null;  
  for ( Node<E> next = first.next; next != null; next = first.next) {  
    first.next = prev;  
    prev = first;  
    first = next;  
  }  
  first.next = prev;  
}

answered Oct 05 '13 at 16:59

user2848321

1

karansingh1487 · Answer 7 · 2014-03-21T06:30:47.367

-1

Modifying the Node Class

u can override toString method in Node class to input any data

public class Node { public Node node; private int data; Node(int data) { this.data = data; } @Override public String toString() { return this.data+""; }

edited Mar 21 '14 at 06:30

answered Mar 21 '14 at 06:23

karansingh1487

105
1
2
11

Reversing a singly linked list iteratively

7 Answers7

Linked