题目:
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?
分析:
分别用迭代和递归来实现.
迭代就是新建一个 newhead 节点, 遍历原链表, 将每一个 node 接到 newhead, 注意保存 head->next 用来更新 head.
递归则是利用函数先走到链表尾端, 依次更新每一个 node 的 next, 最后返回 newhead.
程序:
- //iteratively
- class Solution {
- public:
- ListNode* reverseList(ListNode* head) {
- ListNode *newhead = NULL;
- while(head){
- ListNode *p = head->next;
- head->next = newhead;
- newhead = head;
- head = p;
- }
- return newhead;
- }
- };
- //recursively
- class Solution {
- public:
- ListNode* reverseList(ListNode* head) {
- if (head == NULL || head->next == NULL){
- return head;
- }
- ListNode* newhead = reverseList(head->next);
- head->next->next = head;
- head->next = NULL;
- return newhead;
- }
- };
来源: http://www.bubuko.com/infodetail-2972991.html