2018/06/17
4,185
一 链表倒置
链表倒置是链表的基本操作之一。
题目 一 Reverse Linked List
LeetCode 206 Reverse Linked List
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?
题目提示可以用 迭代 或 递归 两种方法来解。
- 迭代方法
如图:两个指针
head
p
分别指向 表头,欲倒置的元素. 为了使下一个欲倒置的元素不会 野 掉, 还需要一个指针tmp
来保护它- p->next 指向 head
- head->next 指向 tmp
- head = p, p = tmp, tmp 保护下一个欲倒置的元素
代码:
12345678910111213141516171819202122class Solution {public:ListNode* reverseList(ListNode* head) {if(!head) return NULL;if(!head->next) return head;ListNode *p,*tmp;p = head->next;tmp = p->next;head->next = NULL;while(p1){p->next = head;head = p;p = tmp;if(tmp)tmp = tmp->next;}return head;}};
- 递归方法
思想和上面一样,只不过代码的写法不同:12345678910111213class Solution {public:ListNode* reverseList(ListNode* head) {if(!head || !head->next){return head;}ListNode* p = reverseList(head->next);head->next->next = head;head->next = NULL;return p;}};递归的方法代码简洁高效,在很多链表题目中都会用到它,所以特别重要。例如下一题