【剑指Offer 16】反转链表

题目：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

解法1：记录3个结点：当前处理结点、前驱结点、后继结点

代码如下：

package demo;

public class Test16 {
    public static class ListNode {
        int value;
        ListNode next;
    }

    /**
     * 记录3个结点：当前处理结点、前驱结点、后继结点
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        ListNode reverseHead = null; // 反转后的链表头结点
        ListNode curr = head; // 当前处理的结点
        ListNode pre = null; // 当前处理的结点的前驱结点
        ListNode next = null; // 当前处理的结点的后继结点
        while(curr != null) {
            // curr后面的指针会断开，因此先记录后继结点
            next = curr.next;
            // 如果后继结点为空，说明该结点为尾结点，也就是反转后的结点的头结点
            if(next == null) {
                reverseHead = curr;
            }
            // 把curr的下一个结点指向它的前驱结点
            curr.next = pre;
            
            // 把当前结点作为前驱结点
            pre = curr;
            // 将之前的后继结点作为当前处理的结点，继续向下处理
            curr = next;
        }
        return reverseHead;
    }

    public static void printList(ListNode head) {
        while(head != null) {
            System.out.print(head.value + "->");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        ListNode head = new ListNode();
        head.value = 1;
        head.next = new ListNode();
        head.next.value = 2;
        head.next.next = new ListNode();
        head.next.next.value = 3;
        head.next.next.next = new ListNode();
        head.next.next.next.value = 4;
        head.next.next.next.next = new ListNode();
        head.next.next.next.next.value = 5;
        head.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.value = 6;
    
        System.out.println("打印原单链表：");
        printList(head);
        System.out.println("反转后的单链表的头结点：");
        ListNode reverseHead = reverseList(head);
        System.out.println(reverseHead.value);
        System.out.println("打印反转后的单链表：");
        printList(reverseHead);
    }
}

运行结果

解法2：借助临时结点

代码如下：

package demo;

public class Test16 {
    public static class ListNode {
        int value;
        ListNode next;
    }

    /**
     * 借助临时结点
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        // 创建一个临时结点
        ListNode tmp = new ListNode();
        // 临时结点的后继结点为空
        tmp.next = null;
        // 反转后的链表头结点
        ListNode reverseHead = null;
        // 当前处理结点
        ListNode curr = head;
        // 当前处理结点的下一个结点
        ListNode next = null;
        while(curr != null) {
            // curr后面的指针会断开，因此先记录后继结点
            next = curr.next;
            if(next == null) {
                reverseHead = curr;
            }
            // 将当前结点的后继结点指向临时结点的后继结点
            curr.next = tmp.next;
            // 将当前结点作为临时结点的后继结点
            tmp.next = curr;
            // 将下一个待处理结点作为当前结点，继续向下处理
            curr = next;
        }
        return reverseHead;
    }

    public static void printList(ListNode head) {
        while(head != null) {
            System.out.print(head.value + "->");
            head = head.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        ListNode head = new ListNode();
        head.value = 1;
        head.next = new ListNode();
        head.next.value = 2;
        head.next.next = new ListNode();
        head.next.next.value = 3;
        head.next.next.next = new ListNode();
        head.next.next.next.value = 4;
        head.next.next.next.next = new ListNode();
        head.next.next.next.next.value = 5;
        head.next.next.next.next.next = new ListNode();
        head.next.next.next.next.next.value = 6;
    
        System.out.println("打印原单链表：");
        printList(head);
        System.out.println("反转后的单链表的头结点：");
        ListNode reverseHead = reverseList(head);
        System.out.println(reverseHead.value);
        System.out.println("打印反转后的单链表：");
        printList(reverseHead);
    }
}

来源：http://blog.csdn.net/derrantcm/article/details/46678155