【图解算法】链表（上）链表反转、回文判断

链表的题目比较基础，但是越基础的题目就越考验代码功底，这几道题都是面试热题，大家务必掌握。面试时不必一次性给出最优解，而是从最简单的解决办法开始，一步一步优化。因为写得有点长，所以分为两部分。

问题描述

1. 单链表和双向链表的反转。
2. 打印两个有序链表的公共部分。
3. 判断一个链表是否回文结构。

单链表反转

这题相对基础，一般会出现在面试中的第一道题，且可能要求写出递归和非递归的两种解法，如何又快又准地写出来是具有一定挑战性的，读者们不妨在脑海中思考下两种解法的轮廓，再结合文章看看有无遗漏之处。

首先来看看单链表的结构：

struct ListNode {
    int val; // 当前节点值
    ListNode *next; // 指向下一个节点
  
    ListNode(int x) : val(x), next(NULL) {} // 构造函数
};

首先来看看递归解法：

将链表分为两部分：head所在的头节点，已经反转了的部分reverse(head->next)：

注意，这里该如何理解已经反转了的部分呢？我们假设我们已经完成了反转函数ListNode* reverse(ListNode *head)，我们将head->next传入，则能得到反转后的头节点，因此下图中reverse(head->next)指向3。

接下来我们只需将这两部分进行反转即可，为此，我们得先获取反转部分的最后一个节点：

ListNode *p = reverse(head->next);
while(p != nullptr) {
    p = p->next;
}

接下来，进行反转，head的下一个应该是NULL，而p的下一个为head：

完成了调转后，我们应该返回当前的头节点，也就是reverse(head->next)所指向的位置，完整代码如下：

ListNode *reverse(ListNode *head) { // 递归解法
    if (head == nullptr || head->next == nullptr) // 边界处理
        return head;
    ListNode *newHead = reverse(head->next);
    
    ListNode *p = newHead; // 获取后部分的最后一个节点指针
    while (p->next != nullptr) {
        p = p->next;
    }
    // 进行反转
  	head->next = nullptr;
    p->next = head;
    return newHead; // 返回当前头节点
}

接下来，我们看看非递归解法：

首先，我们使用两个指针进行移动标记：pre指向前一个节点，cur为当前节点，因为head处没有前一个节点，所以pre初始化为NULL。

接下来反转节点1：

先用temp指针记录cur->next：

然后当前节点的next指向pre节点：

再往下，则移动pre和cur指针：

重复上述步骤，直到cur == NULL，反转完成，返回pre指针即可：

完整代码：

ListNode *reverse(ListNode *head) { // 非递归解法
    ListNode *pre = nullptr;
    ListNode *cur = head;
    while (cur != nullptr) { // 移动 pre 和 cur，对所有节点进行反转
        ListNode *temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

双向链表反转

前面讲完了单向链表的反转，双向链表实际上只是在前者的基础上增加对pre指针的考量：

struct ListNode {
    int val;
    ListNode *pre; // 指向前一个节点
    ListNode *next;

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

在递归解法中，要注意的head的pre指针：

ListNode *reverse(ListNode *head) { // 递归解法
    if (head == nullptr)
        return head;
    if (head->next == nullptr) { // 不同点1：边界处理也要考虑到对pre指针的处理
        head->pre = nullptr;
        return head;
    }
    ListNode *newHead = reverse(head->next);
    ListNode *p = newHead; // 获取后部分的最后一个节点指针
    while (p->next != nullptr) {
        p = p->next;
    }
  	// 反转链表
  	head->next = nullptr;
    head->pre = p; // 不同点2：增加对head的pre指针的处理
    p->next = head;
    return newHead;
}

而在非递归解法中：

ListNode *reverse(ListNode *head) { // 非递归解法
    ListNode *pre = nullptr;
    ListNode *cur = head;
    while (cur != nullptr) {
        ListNode *temp = cur->next;
        cur->pre = cur->next; // 增加对pre指针的处理
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre;
}

打印两个有序链表的公共部分。

【题目】
给定两个有序链表的头指针head1和head2，打印链表的公共部分。
【解析】

这题实际上比较简单，但要注意理解题意，所谓有序链表，就是指按（升）序排列的链表，所谓公共部分，是指值相等的部分。如果面试过程中发现题意不是很清晰，是可以问面试官确认题意的。

【解答】

解法上就比较简单了，先来看一个例子：

我们每次对head1和head2的值进行比较，如果head1的值小于head2的值，那么head1向后移动，将移动后的head1与head2再次进行比较，相同则输出，否则按谁小谁动的规则，直到head1或head2为NULL。

因为head1->val == head2->val，所以输出head1->val，然后head1和head2一起向前移动：

如此往返，直到其中一个等于NULL，即停止。

代码如下：

void printPublicPart(ListNode *head1, ListNode *head2) {
    while (head1 != nullptr && head2 != nullptr) {
        if (head1->val > head2->val) { // 谁小谁动
            head2 = head2->next;
        } else if (head1->val < head2->val) { // 谁小谁动
            head1 = head1->next;
        } else { // 相等则输出
            cout << head1->val << " ";
            head1 = head1->next;
            head2 = head2->next;
        }
    }
}

判断一个链表是否回文结构

【题目】 给定一个链表的头节点head，请判断该链表是否为回文结构。 例如:

1->2->1，		返回true。 
1->2->2->1，	返回true。 
15->6->15，	返回true。 
1->2->3，		返回false。

【进阶】如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)。

【普通解法】

利用栈结构，我们将链表存起来，存完之后，再一个一个倒出来，同时遍历链表，将链表的节点和栈中取出的节点一一比较，但凡一个不同，则说明链表不是回文结构。

如上图所示，我们先遍历一遍链表，将其节点一个个放入栈中， 这时从栈中推出的话就等于逆序遍历链表，再次顺序遍历链表，与栈中推出的节点比较，那么就相当于两个指针，分别指向链表的开始和结尾，一个往后移动，一个往前移动。如果两个指针指向的节点的值都相等，那么说明这个链表就是回文结构。

代码如下：

bool isPalindrome(ListNode *head) { // 使用栈，空间复杂度 O(N)，时间复杂度 O(N)
    stack<int> listStack;
    ListNode *p = head;

    while (p != nullptr) { // 第一遍遍历，将链表放入栈中
        listStack.push(p->val);
        p = p->next;
    }
    p = head;
    while (p->next != nullptr) { // 第二遍遍历，两者从头一起往后移动
        int top = listStack.top();
        if (p->val != top) {
            return false;
        }
        listStack.pop();
        p = p->next;
    }
    return true;
}

【N/2的空间优化】

事实上，我们并不需要把所有节点都推入栈中，只需要一半即可。我们将链表划分为左右两半，然后将右半部分压入到栈中，再对链表的左半部分做一次遍历，同时弹出栈中节点进行比较。

来看一个例子：

左边的栈是我们压入的右半部分节点，右边是我们对一个奇数个链表的划分（偶数个节点的链表怎么分左右就不用我说了吧，各一半就是了）。

接下来我们需要知道链表中如何快速找到中点：快慢指针

如上图所示，当fast->next == NULL || fast->next->next == NULL时，slow所在位置就是中点，（偶数个时，slow会位于右半区的第一个，奇数个时，如上图所示，位于中间，也就是右半区的前一个，所以我们需要进行调整）

注意这里的条件fast->next == NULL || fast->next->next == NULL，为什么不写成fast == NULL || fast->next == NULL呢？读者们可以思考一下。

事实上，在奇数个的链表中，这两种写法都能使得slow指针到达中点，但是对偶数个节点的链表来说，两种写法会影响最后slow的位置，多一个next，会使得slow多走一步，看看下图就明白了。

我们采用后者，这样可以和奇数个的统一起来slow->next得到右半部分的起始位置：

ListNode *getMid(ListNode *head) { 
    ListNode *slow = head, *fast = head;
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;          // 慢指针每次移动一步
        fast = fast->next->next;    // 快指针每次移动两步
    }
    return slow;
}
// 获取右半区第一个节点的指针
ListNode *right = getMid(head)->next;

当我们获取了右半部分的起始指针后，接下来就很简单了，先将右半部分全部入栈，然后再从左半部分开始，同时弹栈，比较二者。

bool isPalindrome(ListNode *head) {
    ListNode *left = head;
  	ListNode *right = getMid(head)->next; // 获取右半部分起始位置
    stack<int> rightStack;
    while (right != nullptr) { // 将右半部分入栈
        rightStack.push(right->val);
        right = right->next;
    }
    while (rightStack.empty()) { // 栈非空，则继续比较
        if (left->val != rightStack.top()) { // 如果左半部分和弹出的栈顶不同，说明为假
            return false;
        }
        left = left->next;
        rightStack.pop();
    }
    return true;
}

【O(1)的空间优化】

要将空间复杂度优化到O(1)，还是比较考验技巧的，前面我们已经谈到了如何获取中间节点，接下来我们说说如何不使用栈：直接将后半部分原地反转：

如上图所示，我们将链表转成上述结构后，只要分别从头和尾开始，同时比较，只要有不同则说明不是回文结构。至于如何原地反转：

ListNode *getReverseRight(ListNode *head) { // 获取反转后的右起始节点
    // 获取中点
    ListNode *pre = getMid(head);
    ListNode *cur = pre->next;
    pre->next = nullptr; // 将中点的 next 置空
    while (cur != nullptr) {
        ListNode *temp = cur->next;
        cur->next = pre;
        pre = cur;
        cur = temp;
    }
    return pre; // 此时 pre 指向反转后的右半部分的起始节点
}

偶数个节点的链表的反转结果：

接下来只要从head和pre开始，两两比较即可：

bool isPalindromeNoStack(ListNode *head) {
    ListNode *right = getReverseRight(head);
    while (head != nullptr && right != nullptr) {
        if (head->val != right->val) {
            return false;
        }
        head = head->next;
        right = right->next;
    }
    return true;
}

欢迎大家关注我的公众号了解更多内容。