206.Reverse Linked List

Tags; Easy Link List

Link: https://leetcode.com/problems/reverse-linked-list/

---

Reverse a singly linked list.

---

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

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

---

Answer:

/**
 * 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 head;

        ListNode *dummy = new ListNode(0), *cur = head -> next;
        dummy -> next = head;

        while(cur != NULL)
        {
            head -> next = cur -> next;
            cur -> next = dummy -> next;
            dummy -> next = cur;
            cur = head -> next;
        }

        return dummy -> next;
    }
};

解析：

就地反转法，新建一个数据为0的头节点，cur保存head的下一个节点。图示如下：