LeetCode记录--206.反转链表

题目描述

206. 反转链表
反转一个单链表。

示例

  • 输入:

1->2->3->4->5->NULL

  • 输出:

5->4->3->2->1->NULL

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

题解

迭代方式

  迭代的方式相对简单,就是循环把第一个Node放到第二个Node后面,然后把第二个Node放到第三个Node后面,以此类推.

图示

head next 1 2 3 4 5
  • 首先假设头部Node之前还有个叫prev的Node(NULL),要先把它们两个交换位置.

  • 直接将head的next设置成prev就可以交换位置了.这里就是主要的交换的代码,后面的就是移动链表到下一个

  • 这个时候,链表需要向头部移动,也就是将head设置成head的next,不过在这之前还得将head保存到prev里面

  • 判断head是否为空,如果不为空则跳到第一步重复上面的操作
    注:由于head为空时跳出循环,所以直接返回head是不行的,需要返回prev,最后一次循环时,它已经是链表头部了

递归方式

提交代码

迭代方式

  • C语言

执行用时: 8 ms, 在所有 C 提交中击败了59.94%的用户
内存消耗: 7.7 MB, 在所有 C 提交中击败了5.08%的用户

1
2
3
4
5
6
7
8
9
10
11
struct ListNode* reverseList(struct ListNode* head){
struct ListNode *prev = NULL;
while(head)
{
struct ListNode *next = head->next;
head->next = prev;
prev = head;
head = next;
}
return prev;
}

递归方式

  • C语言

执行用时: 8 ms, 在所有 C 提交中击败了59.94%的用户
内存消耗: 7.7 MB, 在所有 C 提交中击败了5.08%的用户

1
2
3
4
5
6
7
8
9
10
11
12
struct ListNode *reverseList(struct ListNode *head)
{
if (head == NULL || head->next == NULL)
{
return head;
}
struct ListNode *next = head->next;
struct ListNode *newHead = reverseList(next);
next->next = head;
head->next = NULL;
return newHead;
}