链表逆序

佚名 6年前 (2019-04-10) 随笔 2036人围观抢沙发百度已收录

问题来源：选自LeetCode 206：反转链表

问题描述：

　　反转一个单链表。

　　示例:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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

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

题目给定信息：

问题分析：

　　一直链表的头结点指针，再不申请额外空间的情况下实现链表的逆序，我们的思路就是循环遍历整个链表，做到每遍历一个链表节点，就逆置一个链表节点，先创建一个新链表的头结点指针new_head并赋值为空，通过修改head指针和new_head指针的指向关系来实现该功能。

函数实现：

 1 public ListNode reverseList(ListNode head) {
 2         ListNode new_HeadListNode=null;
 3         while(head!=null){
 4             //保存原链表当前head指针的下一个节点的位置
 5             ListNode temp=head.next;
 6             //把当前head指针的下一个位置指向new-head
 7             head.next=new_HeadListNode;
 8             //保证每次的new_head指针都是新链表的表头位置
 9             new_HeadListNode=head;
10             //把刚才在temp变量中保存的head指针的下一个位置赋值给head
11             head=temp;
12         }
13         return new_HeadListNode;
14     }