对单链表进行反转有迭代法和递归法两种。

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 || head->next == NULL)     // 空链或只有一个结点，直接返回头指针

        {

            return head;

        }

        else                                        // 至少有两个结点

        {

            ListNode * p1 = head;                   // 第一个结点

            ListNode * p2 = p1->next;               // 第二个结点

            ListNode * p3 = p2->next;               // 第三个结点

            while (p2)                              // 第二个结点为空，到链尾，结束

            {

                p3 = p2->next;

                p2->next = p1;                      // 第二个结点指向第一个结点，进行反转

                p1 = p2;                            // 第一个结点往后移

                p2 = p3;                            // 第二个结点往后移

            }

            head->next = NULL;          // 第一个结点也就是反转后的最后一个节点指向 NULL

            head = p1;                  // 头结点指向反转后的第一个节点

            return head;

        }

    }

};

2. 递归法

• 基线条件：空链或只有一个结点，直接返回头指针
• 递归条件：递归调用，返回子链表反转后的头指针

Solution {

public:

    ListNode* reverseList(ListNode* head) {

        if (head == NULL || head->next == NULL)     // 空链或只有一个结点，直接返回头指针

        {

            return head;

        }

        else                                        // 有两个以上结点

        {

            ListNode *new_head = reverseList(head->next); // 反转以第二个结点为头的子链表

            // head->next 此时指向子链表的最后一个结点

            // 将之前的头结点放入子链尾

            head->next->next = head;

            head->next = NULL;

            return new_head;

        }

    }

};

获取更多精彩，请关注「seniusen」!