反转链表

一、要求

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

链表结点定义为：

 public class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

二、解法

这里我们采用两种方法，分别是迭代与递归。

（1）迭代

从链表头部开始处理，我们需要定义三个连续的结点pPre，当前需要反转的结点pCur，下一个需要反转的结点pFuture和一个永远指向头结点的pFirst。每次我们只需要将pPre指向pFuture，pCur指向pFirst，调整头结点pFirst，调整当前需要反转的结点为下一个结点即pFuture，最后调整pFuture为pCur的next结点。

代码演示

public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        //始终指向链表的头结点
        ListNode pFirst = head;
        //三个结点中的第一个结点
        ListNode pPre = pFirst;
        //当前需要反转的结点
        ListNode pCur = head.next;
        //下一次即将需要反转的结点
        ListNode pFuture = null;
        while (pCur != null) {
            pFuture = pCur.next;
            pPre.next = pFuture;
            pCur.next = pFirst;
            pFirst = pCur;
            pCur = pFuture;
        }
        return pFirst;
    }

反转过程如下

代码提交结果：

（2）递归

递归与迭代不同，递归是从链表的尾结点开始，反转尾结点与前一个结点的指向。

代码演示：

public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pNext = head.next;
        head.next = null;
        ListNode reverseListNode = reverseList2(pNext);
        pNext.next = head;
        return reverseListNode;
    }

反转的过程为：

代码提交结果：

三、整个测试代码

package leetcode.day1006;


/**
 * Created by 戚春阳 2018/10/6
 * 反转单链表
 */
public class ReverseListNode {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 迭代方式
     *
     * @param head 翻转前链表的头结点
     * @return 翻转后链表的头结点
     */
    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        //始终指向链表的头结点
        ListNode pFirst = head;
        //三个结点中的第一个结点
        ListNode pPre = pFirst;
        //当前需要反转的结点
        ListNode pCur = head.next;
        //下一次即将需要反转的结点
        ListNode pFuture = null;
        while (pCur != null) {
            pFuture = pCur.next;
            pPre.next = pFuture;
            pCur.next = pFirst;
            pFirst = pCur;
            pCur = pFuture;
            System.out.println("迭代的反转过程:" + getList(pFirst));
        }
        return pFirst;
    }

    /**
     * 递归方式
     *
     * @param head 翻转前链表的头结点
     * @return 翻转后链表的头结点
     */
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pNext = head.next;
        head.next = null;
        ListNode reverseListNode = reverseList2(pNext);
        pNext.next = head;
        System.out.println("递归的反转过程:" + getList(reverseListNode));
        return reverseListNode;
    }

    /**
     * 将数组转化为链表
     *
     * @return 链表的头结点
     */
    public ListNode setList() {
        int a[] = {1, 2, 3, 4, 5};
        ListNode pHead = new ListNode(a[0]);
        ListNode pNext = pHead;
        for (int i = 1; i < a.length; i++) {
            ListNode pTemp = new ListNode(a[i]);
            pNext.next = pTemp;
            pNext = pTemp;

        }
        return pHead;
    }

    /**
     * @param pHead 链表头结点
     * @return 链表的字符串表达形式
     */
    public String getList(ListNode pHead) {
        int a[] = new int[5];
        ListNode pCur = pHead;
        int point = 0;
        while (pCur != null) {
            a[point] = pCur.val;
            pCur = pCur.next;
            point++;
        }
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        for (int temp : a) {
            sb.append(temp + " ");
        }
        sb.append("]");
        return sb.toString();

    }

    public static void main(String args[]) {
        ReverseListNode test = new ReverseListNode();

        System.out.println("原始链表为:");
        ListNode node = test.setList();
        System.out.println(test.getList(node));

        System.out.println("-------------------------");

        ListNode nodeReverse = test.reverseList(node);
        System.out.println("迭代的最终结果:" + test.getList(nodeReverse));

        System.out.println("-------------------------");

        //可以将之前反转的链表再反转回来
        ListNode nodeReverse2 = test.reverseList2(nodeReverse);
        System.out.println("递归的最终结果:" + test.getList(nodeReverse2));
    }

}

测试输出为：