剑指Offer——反转链表

1、题目描述

　　输入一个链表，反转链表后，输出新链表的表头。

2、代码实现

package com.baozi.offer;

/**
 * 输入一个链表，反转链表后，输出新链表的表头。
 *
 * @author BaoZi
 * @create 2019-07-11-15:53
 */
public class Offer12 {
    public static void main(String[] args) {
        Offer12 offer12 = new Offer12();
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        ListNode l6 = new ListNode(6);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l5.next = l6;
        l6.next = null;
        ListNode result = offer12.ReverseList(l1);
        ListNode temp = result;
        while (temp != null) {
            System.out.println(temp.val);
            temp = temp.next;
        }
    }

    //根据gang'hao'xiang'f题目的要求是要实现一个链表的反转，那么我们可以重新创建一个新的链表，只是这个新链表创建的
    //过程使用的是头插法，这样新的链表的元素顺序就和原来链表的顺序刚好相反
    public ListNode ReverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode newHead = new ListNode(-1);
        ListNode temp1 = head;
        while (temp1 != null) {
            //先把原来链表的当前节点的next保存起来便于下一次循环的时候使用
            ListNode t = temp1.next;
            //下边这两行代码就是使用的头插法创建单链表（先指定空指针的指向，在修改非空指针的指向）
            temp1.next = newHead.next;
            newHead.next = temp1;
            temp1 = t;
        }
        //因为我们创建的新链表的头节点只是为了便于操作，所以实际返回的时候要把这个头节点去掉
        return newHead.next;
    }
}