206. 反转链表[easy]

LeetCode 算法题停止更新，请移步至 GitHub。

题目地址

206. 反转链表

题目描述

反转一个单链表。

解题方法

1.双指针法

1. 使用两个指针分别表示当前节点的前一个节点和后一个节点。

/**
 * 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) {
        if (head == NULL) return NULL;
        
        ListNode *left = NULL;
        ListNode *right = NULL;
        
        while (head != NULL) {
            right = head -> next; // 后一个节点
            head -> next = left; // 反转当前节点的 next
            left = head; // 后移一个节点
            head = right; // 后移一个节点
        }
        return left;
    }
};

之前在循环中使用的是这段代码，这段代码是有问题的

right -> next = head 这一句，把后面的链给断掉了

right = head -> next;
right -> next = head;
head -> next = left;
left = head;
head = right;

执行用时 : 16 ms, 在Reverse Linked List的C++提交中击败了96.91% 的用户

内存消耗 : 9.3 MB, 在Reverse Linked List的C++提交中击败了8.23% 的用户

时间复杂度：O(n)

空间复杂度：O(1)