问题:
给一个单向链表,把它从头到尾反转过来。比如: a -> b -> c ->d 反过来就是 d -> c -> b -> a 。
这里讲解两种方法:
第一种方法就是把每个Node按照顺序存入到一个stack里面,这样,最后面一个就在最上面了。然后,把每一个再取出来,这样顺序就换过来了。
public static Node reverse(Node head) { Stack<Node> stack = new Stack<Node>(); // put all the nodes into the stack while (head != null) { stack.add(head); head = head.next(); } //reverse the linked list Node current = stack.pop(); head = current; while (stack.empty() != true) { Node next = stack.pop(); //set the pointer to null, so the last node will not point to the first node. next.setNext(null); current.setNext(next); current = next; } return head; }
第二种方法就是利用两个指针,分别指向前一个节点和当前节点,每次做完当前节点和下一个节点的反转后,把两个节点往下移,直到到达最后节点。
public static Node reverse(Node head) { Node previous = null; while (head != null) { Node nextNode = head.next(); head.setNext(previous); previous = head; head = nextNode; } return previous; }