Invert linear linked list

a linear linked list is a set of nodes. This is how a node is defined (to keep it easy we do not distinguish between node an list):

class Node{
    Object data;
    Node link;

    public Node(Object pData, Node pLink){
        this.data = p开发者_JAVA技巧Data;
        this.link = pLink;
    }

    public String toString(){
        if(this.link != null){
            return this.data.toString() + this.link.toString();
        }else{
            return this.data.toString() ;
        }
    }

    public void inc(){
        this.data = new Integer((Integer)this.data + 1);
    }

    public void lappend(Node list){
        Node child = this.link;
        while(child != null){
            child = child.link;
        }
        child.link = list;
    }

    public Node copy(){
        if(this.link != null){
            return new Node(new Integer((Integer)this.data), this.link.copy());
        }else{
            return new Node(new Integer((Integer)this.data), null);
        }
    }

    public Node invert(){
        Node child = this.link;
        while(child != null){
            child = child.link;
        }
        child.link = this;....
    }
}

I am able to make a deep copy of the list. Now I want to invert the list so that the first node is the last and the last the first. The inverted list has to be a deep copy.

I started developing the invert function but I am not sure. Any Ideas?

Update: Maybe there is a recursive way since the linear linked list is a recursive data structure.

I would take the first element, iterate through the list until I get to a node that has no child and append the first element, I would repeat this for the second, third....

---

I sometimes ask this question in interviews...

I would not recommend using a recursive solution, or using a stack to solve this. There's no point in allocating O(n) memory for such a task.

Here's a simple O(1) solution (I didn't run it right now, so I apologize if it needs some correction).

Node reverse (Node current) {

    Node prev = null;

    while (current != null) {
        Node nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }

    return prev;
}

BTW: Does the lappend method works? It seems like it would always throw a NullReferenceException.

---

There's a great recursive solution to this problem based on the following observations:

1. The reverse of the empty list is the empty list.
2. The reverse of a singleton list is itself.
3. The reverse of a list of a node N followed by a list L is the reverse of the list L followed by the node N.

You can therefore implement the reverse function using pseudocode along these lines:

void reverseList(Node node) {
    if (node == null) return;      // Reverse of empty list is itself.
    if (node.next == null) return; // Reverse of singleton list is itself.

    reverseList(node.next); // Reverse the rest of the list
    appendNodeToList(node, node.next); // Append the new value.
}

A naive implementation of this algorithm runs in O(n²), since each reversal requires an append, which requires an O(n) scan over the rest of the list. However, you can actually get this working in O(n) using a clever observation. Suppose that you have a linked list that looks like this:

n1 --> n2 --> [rest of the list]

If you reverse the list beginning at n2, then you end up with this setup:

n1       [reverse of rest of the list] --> n2
 |                                          ^
 +------------------------------------------+

So you can append n1 to the reverse of the rest of the list by setting n1.next.next = n1, which changes n2, the new end of the reverse list, to point at n1:

[reverse of the rest of the list] --> n2 --> n1

And you're golden! Again more pseudocode:

void reverseList(Node node) {
    if (node == null) return;      // Reverse of empty list is itself.
    if (node.next == null) return; // Reverse of singleton list is itself.

    reverseList(node.next); // Reverse the rest of the list
    node.next.next = node; // Append the new value.
}

EDIT: As Ran pointed out, this uses the call stack for its storage space and thus risks a stack overflow. If you want to use an explicit stack instead, you can do so like this:

void reverseList(Node node) {
    /* Make a stack of the reverse of the nodes. */
    Stack<Node> s = new Stack<Node>();
    for (Node curr = node; node != null; node = node.next)
        s.push(curr);

    /* Start unwinding it. */
    Node curr = null;
    while (!s.empty()) {
        Node top = s.pop();

        /* If there is no node in the list yet, set it to the current node. */
        if (curr == null)
            curr = top;
        /* Otherwise, have the current node point to this next node. */
        else
            curr.next = top;

        /* Update the current pointer to be this new node. */
        curr = top;
    }
}

I believe that this similarly inverts the linked list elements.

---

I would treat the current list as a stack (here's my pseudo code):

Node x = copyOf(list.head);
x.link = null;
foreach(node in list){
    Node temp = copyOf(list.head);
    temp.link = x;
    x = temp;        
}

At the end x will be the head of the reversed list.

---

I more fammiliar whit C, but still let me try. ( I just do not sure if this runs in Java, but it should)

node n = (well first one)
node prev = NULL;
node t;
while(n != NULL)
{
     t = n.next;
     n.next = prev;
     prev = n;
     n = t;
}

---

Reversing a single-linked list is sort of a classic question. It's answered here as well (and well answered), it does not requires recursion nor extra memory, besides a register (or 2) for reference keeping. However to the OP, I guess it's a school project/homework and some piece of advice, if you ever get to use single linked list for some real data storage, consider using a tail node as well. (as of now single linked lists are almost extinct, HashMap buckets comes to mind, though). Unless you have to check all the nodes for some condition during 'add', tail is quite an improvement. Below there is some code that features the reverse method and a tail node.

package t1;

public class SList {
    Node head = new Node(); 
    Node tail = head;

    private static class Node{
        Node link;
        int data;           
    }


    void add(int i){
        Node n = new Node();
        n.data = i;
        tail = tail.link =n;        
    }

    void reverse(){
        tail = head;
        head = reverse(head);
        tail.link = null;//former head still links back, so clear it
    }

    private static Node reverse(Node head){            
        for (Node n=head.link, link; n!=null; n=link){//essentially replace head w/ the next and relink
            link = n.link;
            n.link = head;
            head = n;           
        }
        return head;
    }

    void print(){
        for (Node n=head; n!=null;n=n.link){
            System.out.println(n.data);
        }       
    }

    public static void main(String[] args) {
        SList l = new SList();
        l.add(1);l.add(2);l.add(3);l.add(4);
        l.print();
        System.out.println("==");
        l.reverse();
        l.print();
    }
}

---

I was wondering something like that(I didnt test it, so):

invert(){
  m(firstNode, null);
}

m(Node v, Node bef){
  if(v.link != null)
   m(v.link,v);
  else
   v.link=bef;
}

---

Without much testing,

Node head = this;
Node middle = null;
Node trail = null;
while (head != null) {
    trail = middle;
    middle = head;
    head = head.link;
    middle.link = trail;
}
head = middle;
return head;

---

public ListNode Reverse(ListNode list)
{
    if (list == null) return null; 

    if (list.next == null) return list; 

    ListNode secondElem = list.next;

    ListNode reverseRest = Reverse(secondElem);

    secondElem.Next = list;

    return reverseRest;
}

Hope this helps.