反转一个单链表。 示例: 输入: 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 }View Code