Leetcode206-Reverse Linked List

206. Reverse Linked List

Reverse a singly linked list.

Hint:

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

题目说明：

已知链表的头指针head，将链表逆序而不使用额外的空间。
先给出链表的数据结构：

struct ListNode {
    int val;   // 数据域
    ListNode *next;  // 指针域
    ListNode(int x): val(x), next(NULL) {}  // 构造函数
};

如图：

image.png

解题思路：

方法1：就地逆置法
首先声明一个新链表 头结点的指针 ：ListNode *new_head = NULL；

步骤1：next = head->next

image.png

步骤2：head->next = new_head

image.png

步骤3：new_head = head

image.png

步骤4：head = next

image.png

---

方法2：头插法
首先声明一个新链表 头结点 ：ListNode new_head(0)；

步骤1：next = head->next

image.png

步骤2：head->next = new_head->next

image.png

步骤3：new_head->next = head

image.png

步骤4：new_head->next = head

image.png

---

自此，完成了一个节点的逆置过程；依次遍历链表中的所有节点，可以实现链表的逆序操作；其中要注意的是，头插法返回的应该是除去0节点的 head->next。

---

My Solution 1（C++ 就地逆置法完整实现）

#include <cstdio>
#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
};

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

int main() {
    Solution S;
    ListNode a = ListNode(1);
    ListNode b = ListNode(2);
    ListNode c = ListNode(3);
    ListNode d = ListNode(4);
    ListNode e = ListNode(5);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    ListNode *head = &a;
    while(head) {
        cout << head->val << "->";
        head = head->next;
    }
    cout << endl;
    head = S.reverseList(&a);
    while(head) {
        cout << head->val << "->";
        head = head->next;
    }
    return 0;
}

Result

1->2->3->4->5->
5->4->3->2->1->
Process returned 0 (0x0)   execution time : 0.031 s
Press any key to continue.

My Solution 2（python3 头插法实现）

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        new_head = ListNode(0)
        if head == None:
            return head
        while head:
            next_p = head.next
            head.next = new_head.next
            new_head.next = head
            head = next_p
        return new_head.next