单链表逆转置的递归与非递归方式
Node类
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
先看递归求解:
public ListNode reverse1(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode temp = head.next;
ListNode reversedHead = reverse1(head.next);
temp.next = head;
head.next = null;
return reversedHead;
}
有点难理解,看看debug的图基本上就能懂了。

就是在temp存储了尾节点,然后再一层层往前。这个head.next=null是必须的,因为最后一个节点时不会自己赋值的,会形成一个环。
非递归算法:
public ListNode reverse(ListNode head){
ListNode p = head,q = null,front = null;
while(p!=null){
q = p.next;
p.next = front;
front = p;
p = q;
}
head = front;
return head;
}
这个理解起来就比较简单啦。