剑指 Offer 24. 反转链表

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

示例:

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

限制：

0 <= 节点个数 <= 5000

题目要求将链表反转，我们可以再创建一个链表（含头节点），依次将原先链表中的每次的第一个元素拆下来利用头插法插入第二条链表中，直到原先链表中所有的节点都放入新的链表中，你会发现基本已经实现了链表的反转，最后将原先链表的头节点连接到新的链表上，替换新链表的头节点就完成了链表的反转。根据示例可知，原先链表的头节点是链表第一个元素节点，我们之所以加上头节点是方便我们进行链表节点的移除和加入，最后程序只要返回头节点的next节点就可以了。

示意图：

新建一个链表（只有头节点first），创建一个头节点thehead指向原先节点

cur指向thehead.next，即指向链表第一个元素

 将cur指向的第一个元素移出链表，thehead指向cur.next

 将cur指向的元素放到新的链表中，first指向cur

cur.next = first.next

 再讲cur指向thehead.next

 重复这个过程，直到原先链表中只剩thehead

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode thehead = new ListNode(-6);
        thehead.next = head;
        ListNode first = new ListNode(-5);
        ListNode cur = thehead.next;
        
        while(cur != null){
            thehead.next = cur.next;
            cur.next = first.next;
            first.next = cur;
            cur = thehead.next;
        }
        thehead.next = first.next;
        cur = thehead;
        while(true){
            System.out.print(cur);
            if(cur == null){
                break;
            }
            System.out.print("->");
            cur = cur.next;
        }
        return thehead.next;

    }
}

通过！