Leetcode - 206反转链表

206 反转链表

题目描述

反转一个单链表。

示例： 输入： 1-> 2-> 3-> 4-> 5-> NULL 输出： 5-> 4-> 3-> 2-> 1-> NULL

进阶： 你可以迭代或递归地反转链表你能否用两种方法解决这道题？

题目给出的接口是：

/** * 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) { } };

题目分析

使用递归方法，步骤明显简单一些，但可能不如迭代那么好理解。迭代只需要找到将每一个元素的next的next指向它本身，直到找到最后一个元素即可。但递归则是一直找到最后一个元素，再倒退回来。

递归法

/** * 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 == NULL || head->next == NULL) return head; ListNode *newhead = reverseList(head->next); head->next->next = head; head->next = NULL; return newhead; } };

迭代法

/** * 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) { ListNode *pre = nullptr, *cur = head, *r = nullptr; while (cur != nullptr) { r = cur->next; cur->next = pre; pre = cur; cur = r; } return pre; } };