leetcode解题: Reverse Linked List (206)

发表于 | 分类于

Reverse a singly linked list.
A linked list can be reversed either iteratively or recursively. Could you implement both?

解法1：Iteratively

经典的答案，没啥好说的。要背下来。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 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* ptr = NULL;
        while (head != NULL) {
            ListNode* temp = head->next;
            head->next = ptr;
            ptr = head;
            head = temp;
    }
    return ptr;
    }
};

Java

1

解法2： Recursively

C++

1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
};