206.反转链表

佚名 6年前 (2019-10-23) 算法 2266人围观抢沙发百度已收录

反转一个单链表。示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 1 struct ListNode {
 2     int val;
 3     ListNode *next;
 4     ListNode(int x) : val(x), next(NULL) {}
 5 };
 6 
 7 class Solution {
 8 public:
 9     ListNode* reverseList(ListNode* head) {
10         ListNode *new_head = NULL;//指向新链表头节点的指针
11         while (head) {
12             //备份 head->next,因为第二步要把head->next 指向新的头节点,不保存就找不到了
13             ListNode *next = head->next;
14             head->next = new_head;//更新 head->next,指向新链表的头节点
15             new_head = head;//移动 new_head，指向新节点
16             head = next;
17         }
18         return new_head;
19     }
20 };

测试

 1 int main(int argc, const char * argv[]) {
 2     ListNode a(1);
 3     ListNode b(2);
 4     ListNode c(3);
 5     ListNode d(4);
 6     ListNode e(5);
 7     a.next = &b;
 8     b.next = &c;
 9     c.next = &d;
10     d.next = &e;
11     Solution solve;
12     ListNode *head = &a;
13     cout << "Before\n";
14     while (head) {
15         cout <<head->val<<endl;
16         head = head->next;
17     }
18     head = solve.reverseList(&a);
19     cout << "After\n";
20     while (head) {
21         cout <<head->val<<endl;
22         head = head->next;
23     }
24     
25     return 0;
26 }