【LeetCode】206. 反转链表

反转一个单链表。

示例:

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

【提交代码】

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 
 9 
10 struct ListNode* reverseList(struct ListNode* head){
11     struct ListNode *p;
12     struct ListNode *tmp;
13 
14     if( head == NULL )
15         return head;
16 
17     p = head->next;     // p指向断开的开头，当前要反转的节点
18     head->next = NULL;  // head始终指向反转后新链表的头
19 
20     while( p != NULL )
21     {
22         tmp = p->next;  // 预保存p的下一个节点，下一个要反转的节点
23 
24         p->next = head;
25         head = p;
26 
27         p = tmp;
28     }
29 
30     return head;
31 }

【提交代码】优化代码的写法

 1 struct ListNode* reverseList(struct ListNode* head){
 2     struct ListNode *pre;
 3     struct ListNode *cur;
 4     struct ListNode *tmp;
 5 
 6     pre = NULL;
 7     cur = head;
 8     while( cur != NULL )
 9     {
10         tmp = cur->next;
11 
12         cur->next = pre;
13         pre = cur;
14         cur = tmp;
15     }
16 
17     return pre;
18 }

【解题思路】

注：

找到当前需要反转的节点cur，并且记录其前一个节点pre以及下一个节点tmp_next；

先把cur指向其pre，即反转了当前节点；然后滑动处理下一个节点；