【算法】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;
   }  

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