逆置链表

逆置链表

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }

####迭代法

链表的逆置是常见的也是比较基础的算法考核题目。假设存在链表1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。

逆置链表时，我们需要将当前节点的 next指针改为指向前一个元素。首先curr指向第一个元素，我们需要一个prev来保存前一个元素，将curr后移一个元素，将curr.next赋值给prev。不断循环实现链表逆置，直到curr为空结束循环。

public class Solution {
    public static ListNode reverseList(ListNode head) {
        ListNode nextTemp = null;
        ListNode curr = head;
        ListNode prev = null;
        while (head != null) {
            nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }    

####递归法

这道题递归的思想很有趣，关键在于反向工作。假设列表的其余部分已经被反转，那么如何反转前面部分是我们需要解决的问题。假设列表为：

n1~ → … → nk−1~ → nk~ → nk+1~ → … → nm → ∅

若从节点nk+1到nm已经被反转，而我们正处于nk。

n1~ → … → nk−1~ → nk~ → nk+1~ ← … ← nm

我们希望nk+1的下一个节点指向nk。所以，nk.next.next=nk。需要注意的是n1~的下一个必须指向∅。

public class Solution {
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return p;
    }