Author: hozhangel
Time: 2018-08-11 20:31:01
problem description:
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
My hint:
just one traverse is enough:
step 1: pre->1->2->3->4->5->NULL
||p q
step 2: pre->2->1->3->4->5->NULL
q ||p
step 3: pre->3->2->1->4->5->NULL
q ||p
at every step || (skip to the next node),just move the current node to the pre->next,
My code:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if (head == nullptr || head->next == nullptr) { return head; } ListNode* pre = new ListNode(0); pre->next = head; ListNode* p = pre->next; ListNode* q = head->next; while (q) { ListNode* pt = q; p->next = pt->next; pt->next = pre->next; pre->next = pt; q=p->next; } return pre->next; } };
原文：https://www.cnblogs.com/hozhangel/p/9460938.html