【算法】Java单链表逆转

单链表逆转置的递归与非递归方式

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;//设置q是p结点的后继结点,即用q来保持p的后继结点 p.next = front;//逆转,即使p.next指向p结点的前驱结点 front = p;//front向后移一步 p = q;//p向后移一步 } head = front;//head指向原链表的最后一个结点，完成逆转 return head; }

这个理解起来就比较简单啦。