（转载）漫画：如何将一个链表“逆序”？

数据结构链表转载

发布日期: 2019-03-20

声明：本文转载自微信公众号程序员小灰，以获作者授权转载

------第二天-------

（现实里的小灰在刚入行的时候，面试官也问了我这个问题，当时小灰就傻傻的问面试官是单链表还是双链表？然后就没然后了……）

让我们从链表头部开始，建立三个临时节点的引用，分别为p1，p2，p3。它们分别指向头节点、第二个节点、第三个节点。

实现链表逆序的完整步骤如下：

以p2节点为视角，把p2节点原本指向p3的next指针倒转，指向p1。
三个临时节点引用p1，p2，p3分别向后移动一格位置。
重复第1步的工作，以p2节点为视角，把p2节点原本指向p3的next指针倒转，指向p1。
重复第2步的工作，三个临时节点引用p1，p2，p3分别向后移动一格位置。

…….
…….
继续像这样子迭代下去，一直到p2是空为止。
最后，把head节点的next指向空，成为逆序链表的尾节点。并且把p1赋值给head，让p1所在的节点成为逆序链表的头节点。

Java:

private static Node head;
public static void reverseLinkedList()
{
    if(head == null || head.next == null)
        return;
    Node p1 = head;
    Node p2 = head.next;
    Node p3 = null;
    while(p2 != null)
    {
        p3 = p2.next;
        p2.next = p1;
        p1 = p2;
        p2 = p3;
    }
    head.next = null;
    head = p1;
}

private static class Node
{
    int data;
    Node next;
    Node(int data)
    {
        this.data = data;
    }
}

public static void main(String[] args)
{
    // 初始化链表
    head = new Node(3);
    head.next = new Node(5);
    Node temp = head.next;
    temp.next = new Node(1);
    temp = temp.next;
    temp.next = new Node(4);
    temp = temp.next;
    temp.next = new Node(9);

    // 逆序前输出链表
    temp = head;
    while(temp != null)
    {
        System.out.println(temp.data);
        temp = temp.next;
    }

    // 逆序链表
    reverseLinkedList();

    // 逆序后输出链表
    temp = head;
    while(temp != null)
    {
        System.out.println(temp.data);
        temp = temp.next;
    }
}

C++

#include <iostream>
using namespace std;

class Node
{
public:
    int data;
    Node* next;
    Node(int da, Node* p = nullptr)
    {
        this->data =  da;
        this->next = p;
    }
};

Node* reverseLinkedList(Node *head)
{
    if(head == nullptr || head->next == nullptr)
        return head;
    Node *p1 = head;
    Node *p2 = head->next;
    Node *p3 = nullptr;
    while(p2 != nullptr)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }
    head->next = nullptr;
    head = p1;
    return head;
}

int main()
{
    // 初始化链表
    Node *head;
    head = new Node(3);
    head->next = new Node(5);
    Node *tmp = head->next;
    tmp->next = new Node(1);
    tmp = tmp->next;
    tmp->next = new Node(4);
    tmp = tmp->next;
    tmp->next = new Node(9);

    cout << "逆序前" << endl;
    // 逆序前输出链表
    tmp = head;
    while(tmp != nullptr)
    {
        cout << tmp->data << endl;
        tmp = tmp->next;
    }
    // 逆序链表
    head = reverseLinkedList(head);

    cout << "逆序后" << endl;
    // 逆序后输出链表
    tmp = head;
    while(tmp != nullptr)
    {
        cout << tmp->data << endl;
        tmp = tmp->next;
    }
}