【基础算法】单链表的OJ练习(4) # 分割链表 # 回文链表 #

前言

• 本章的OJ练习相对前面的难度加大了，但是换汤不换药，还是围绕单链表的性质来出题的。我相信，能够过了前面的OJ练习，本章的OJ也是轻轻松松。

• 对于OJ练习(3)：-> 传送门 <- ，着重需要理解的是相交链表那道题的双指针思路，明白为什么可以这样，这样为什么可行。后面遇到类似的题目我还会做么？

• 我们每做一道题目，都要深挖他的题目结构，明白为什么可以这样做。我相信如果你这样去做了，并且不断地练习，到后面，每遇到一个题目，你都会有所印象，并能够很快的指出解这道题的思路。

分割链表

• 题目链接：-> 传送门 <- 。

• 题目描述：现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

• 这里的不能改变原来的数据顺序，也就是比x小的节点放在其余节点之前时，这些节点的顺序应该与没有放之前是一样的。

• 例如: 2 4 8 5 9 3 5 ，给定 x = 8，通过本题目的描述最终的答案应该为：2 4 5 3 5 8 9 。

图解描述：（给定x = 3）

解题思路：

• 根据题目的意思以及不能改变原来的数据顺序这一特性，我们可以以一种反归并的思想来想这道题。

• 我们遍历原链表并创建两个新链表（这里的新链表表示的是在原链表基础上通过某一条件新连接的一串节点），第一个链表用来尾插小于x的节点，第二个链表用来尾插大于等于x的节点，最后再将第一个链表的尾与第二个链表的头相连接，再返回连接后的整个链表的头，便ok啦。整个解题思路大致是这样，后面，来谈谈其中的细节。

• 对于创建的两个新链表，都需要哨兵位的头节点来维护，什么是哨兵位的头节点呢？我们可以把哨兵位的头节点当作真实头节点的前驱，它是一个不在答案范围内的节点，但它却可以有效的控制真实的链表。其里面的值可以是随机的，它的next初始指向NULL，直到有节点尾插，它的next就指向这个节点,而这个节点就是新连接的链表的真实的头。当最后连接完成时，我们想要返回这个链表，应该返回哨兵位的next，因为哨兵位的next才是有效的真实的头节点。

• 如果说不用哨兵位的头节点来维护，也是可以的。不过这样会有很多不必要的处理。比如给的原链表是NULL,或者两个新链表连接完后其中有一个为空，这些都有可能造成解题出问题，因此需要额外的处理。所以，为了减少这些麻烦，用哨兵位的头节点来维护这两个新链表，上述的这些情况都能够有效避之（上手写代码就有深刻的体会）。

• 有了上面的铺垫我们只需要按照题目要求依次在原链表取节点，然后在对应哨兵位节点指向的链表中尾插，最后将这两个链表连接即可。

下面是代码实现：

这里没学过c++也不用担心，代码纯都是C语言写的。

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// 创建两个哨兵位的头节点// nhead作为连接比x小的节点// rhead作为连接大于等于x的节点struct ListNode* nhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* rhead = (struct ListNode*)malloc(sizeof(struct ListNode));// 操控连接的指针nhead->next = NULL, rhead->next = NULL;struct ListNode* cur = pHead, * cur1 = nhead, * cur2 = rhead;// 遍历原链表while (cur){// 如果小于x就尾插到nheadif (cur->val < x) {cur1->next = cur;cur1 = cur1->next;}else   // 如果 >= x 就尾插到rhead{cur2->next = cur;cur2 = cur2->next;}cur = cur->next;}// 两个带哨兵位头节点的链表的连接// 第一个的尾连接第二个的头cur1->next = rhead->next;// 将第二个的尾置为NULLcur2->next = NULL;// 保存连接好的整个链表的头节点（哨兵位头节点的下一个）struct ListNode* newhead = nhead->next;// 分别释放创建的两个哨兵位头节点free(nhead);free(rhead);// 返回新链表的头return newhead;}
};

---

回文链表

• 题目链接：-> 传送门 <- 。

• 题目描述：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

• 回文结构，相信大家已不陌生，类似于12321，123321，6789876这样的数字，都可称之为回文数。而回文链表也是一样，它每个节点的值组成的数就是一个回文数，例如下面这些链表：

• 那么我们该如何判断一个链表是否为回文链表呢？

解题思路一：

• 我们可以在不破坏原链表的情况下另外创建一个链表，通过遍历原链表依次将原链表上的节点复制尾插到新链表。

• 然后两个链表从头开始比较，如果有一个节点的值不相等就返回false。两个链表都遍历结束并且最后遍历的指针都同时指向NULL，此时返回true。

下面是代码实现：

bool isPalindrome(struct ListNode* head){struct ListNode* rhead = NULL;struct ListNode* cur = head;// 尾插到新链表while (cur){if (rhead == NULL){rhead = (struct ListNode*)malloc(sizeof(struct ListNode));rhead->val = cur->val;rhead->next = NULL;}else {struct ListNode* newnode = (struct ListNode*)malloc(sizeof(struct ListNode));newnode->val = cur->val;newnode->next = rhead;rhead = newnode;}cur = cur->next;}struct ListNode* cur1 = head, * cur2 = rhead;while (cur1 && cur2){// 有不同直接返回falseif (cur1->val != cur2->val) return false;cur1 = cur1->next;cur2 = cur2->next;}// 如果结束且同时指向NULL，说明回文if (cur1 == NULL && cur2 == NULL) return true;else return false;
}

该思路可以说是暴力解法，效率相对较低，并且开了额外的空间，如果限制不能开额外的空间呢？

解题思路二：

• 上一个思路创建了额外的空间，而本思路将不创建新的空间。

• 首先，找到链表的中间节点，然后从这个中间节点开始，将后面的节点逆转，最后从链表的头节点和逆转后返回的节点分别开始遍历判断。

• 如下图解析：

• 可以看到，整个判断过程是一个循环，如果rhead指向空就结束循环，说明是回文链表；如果在循环期间，发现有不一样的值的节点，就直接返回false。

• 对于 -> 找中间节点 <- 和 -> 反转链表 <- ，在前面已经讲解过了，在这里，我们直接 ctrl + c , ctrl + v 就好。

下面是代码实现：

// 寻找中间节点函数
struct ListNode* middleNode(struct ListNode* head){struct ListNode* fast = head, * slow = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;
}// 反转链表函数
struct ListNode* reverseList(struct ListNode* head){struct ListNode* cur = head;struct ListNode* prev =  NULL;while (cur){struct ListNode* tmp = cur->next;cur->next = prev;prev = cur;cur = tmp;}return prev;
}bool isPalindrome(struct ListNode* head){// 找中间节点struct ListNode* mid = middleNode(head);// 从中间节点开始反转链表struct ListNode* rlist = reverseList(mid);// 判断while (rlist){if (head->val != rlist->val) return false;rlist = rlist->next;head = head->next;}       return true;
}

---

写在最后

对于单链表的题目练习，最重要的是思路，我们在数据结构阶段要养成画图的习惯，因为它能帮助我们更好的理解。后续还会有单链表相关的题目练习。

感谢阅读本小白的博客，错误的地方请严厉指出噢！