反转链表解决

反转一个单链表。

示例:

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

解决思路：先构建一个虚拟头节点dummyhead，通过遍历获取每一个节点cur，插入在虚拟头节点那个树上了，具体是cur.next=dummyhead.next,dummyhead.next=cur，这句话是把cur指向dummyhead的下一个节点（前一个节点），然后dummyhead再指向cur，cur再遍历最后返回dummyhead。next就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode re(ListNode head){
        ListNode reverse=new ListNode(-1);
        ListNode cur=head.next;
        ListNode next;
        while (cur!=null){
            next=cur.next;
            cur.next=reverse.next;//把获取的这个节点指向rever节点的下一个
            //1  2  3原来的
            //0reverse
            //先是1.next=null，再0指向1   0  1  null
            reverse.next=cur;//重新链接，使revers节点下一个变成获取的
            cur=next;
        }
        head.next=reverse.next;//reverse已经被取代了
        return head;
    }