链表的逆序

有两种方法,时间复杂度都是O(n)

第一种：非递归的算法。

设置两个临时指针prev和next分别标记当前结点的前驱和后继，将当前结点的next指针指向前驱，然后把前驱指针替换为当前结点，当前结点替换为next，即向“后”移动，直到链表空了（next为NULL）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

 // 1 <-2 3
public class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null) return head;

        ListNode pre = head;
        ListNode p = head.next;
        pre.next = null;
        ListNode nxt;
        while(p!=null) {
            nxt = p.next;
            p.next = pre;
            pre = p;
            p = nxt;
        }
        return pre;
    }
}

第二种：递归的算法。

递归算法描述：要将当前结点逆序，那么先将它的后继结点都逆序，然后把逆序后的尾结点的next指向当前结点即可。

1 recursion

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
	//如果头节点为空，或者头结点的下一个节点为空，直接返回头节点
        if(head==null) return null;
        if(head.next==null) return head;

        ListNode p = head.next;//从链表的第二个节点开始子链表递归
        ListNode n = reverseList(p);  //返回新的头结点，返回的是reverse好的新头节点

	//重建老的头结点head和第二个节点p之间的关系。
        head.next = null;  //老的头结点为空
        p.next = head;  //第二个节点p指向老的头结点
        return n;
    }
}