LeetCode 206——反转链表-白红宇

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

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」!