题目链接：Reverse Linked List

Reverse a singly linked list.

Hint:

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

这道题的要求是反转链表。

  1. 迭代

新建一头指针h，每次从head读取1个节点，并插入到h的首位置。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution
{
public:
    ListNode* reverseList(ListNode* head)
    {
        ListNode *h = NULL;
        
        while(head != NULL)
        {
            ListNode *temp = head;
            head = head -> next;
            
            temp -> next = h;
            h = temp;
        }
        
        return h;
    }
};

  1. 递归

递归过程中，将链表分为两部分：已反转（h）和未反转（head）。当head为NULL时结束递归。每次将head节点next指针指向h，然后更新h为head，head后移一位。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution
{
public:
    ListNode* reverseList(ListNode *head)
    {
        return reverseList(head, NULL);
    }
private:
    ListNode* reverseList(ListNode *head, ListNode *h)
    {
        if(head == NULL)
            return h;
        
        ListNode *next = head -> next;
        head -> next = h;
        return reverseList(next, head);
    }
};