LeetCode 206——反转链表

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

1. 迭代法

• 迭代法从前往后遍历链表，定义三个指针分别指向相邻的三个结点，反转前两个结点，即让第二个结点指向第一个结点。然后依次往后移动指针，直到第二个结点为空结束，再处理链表头尾即可。

1.png 2.png 3.png 4.png 5.png

/**
 * 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. 递归法

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

6.png 7.png 8.png 9.png

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

seniusen