Reverse Linked List

Veröffentlicht am   |   in   |  

题目：
https://leetcode.com/problems/reverse-linked-list/

Reverse a singly linked list.

翻转一个链表。数据结构如下

1
2
3
4
5
6
7
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/

使用迭代的方法很容易（好吧，一开始我写的代码很丑陋，下面是leetcode给的答案：

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

使用递归写出的代码更加简洁：

1
2
3
4
5
6
7
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

显然两种方法的复杂度都是O(n)