文章目录
- 21. 合并两个有序链表
- CM11 链表分割
- OR36 链表的回文结构
- 160. 相交链表
21. 合并两个有序链表
题目链接
思路
该题的思路比较简单，我们只需创建一个头结点，然后从两个链表的表头开始依次比较传入的两个链表的结点的大小，并将两个链表中较小的结点尾插到新链表的后面即可。
注意两点：
1.在尾插过程中，若某一链表已被遍历完毕，则直接将另一个未遍历完的链表剩下的结点尾插到新链表后面即可。
2.函数返回的时候，不是返回头结点的地址，而是第一个结点的地址，所以我们要返回头结点指向的位置并将头结点释放。
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* newhead = new ListNode(-1,nullptr); //创建头结点ListNode* cur = newhead; //记录头节点ListNode* cur1 = list1;ListNode* cur2 = list2;while(cur1 && cur2){if(cur1->val > cur2->val){newhead->next = cur2;newhead = cur2;cur2 = cur2->next;}else{newhead->next = cur1;newhead = cur1;cur1 = cur1->next;}}while(cur1) //将未遍历完的链表连入{newhead->next = cur1;newhead = cur1;cur1 = cur1->next;}while(cur2){newhead->next = cur2;newhead = cur2;cur2 = cur2->next;}return cur->next;}
};
CM11 链表分割
题目链接
思路
创建两个链表，遍历一遍传入的链表，将值大于x的结点和值小于x的结点依次尾插到两个链表中，最后再将这两个链表链接起来，并返回第一个结点的位置即可。
1.把小于x的结点尾插到less链表，把大于x的结点尾插到greater链表。
注意：
1.链接后的链表的最后一个结点的指针域需要置空，否则可能造成链表成环。
2.返回的头指针应是lessHead->next，而不是lessHead。
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code hereListNode* lesstail = new ListNode(-1);ListNode* greattail = new ListNode(-1);ListNode* lesshead = lesstail;ListNode* greathead = greattail;ListNode* cur = pHead;while(cur){if(cur->val < x){lesstail->next = cur;lesstail = cur;cur = cur->next;}else{greattail->next = cur;greattail = cur;cur = cur->next;}}greattail->next = nullptr; //置空是为了防止之前的那个连接存在，会成环lesstail->next = greathead->next;return lesshead->next;}
};
OR36 链表的回文结构
题目链接
思路
我们需要找到传入链表的中间结点，并将中间结点及其后面结点进行反转，然后再将原链表的前半部分与反转后的后半部分进行比较，若相同，则该链表是回文结构，否则，不是回文结构。
1.找到链表的中间结点。
2.反转中间结点及其后面的结点。
3.比较链表的前半部分与后半部分的结点值，若相同则是回文结构，否则，不是回文结构。
将A指针指向的结点与RHead指针指向的结点进行比较，若相同，则两个指针后移，继续比较后面的结点，直到RHead指针指向NULL时，比较结束。
注意：就算传入的链表是结点数为奇数的回文结构，该思路也可以成功判断。
class PalindromeList {
public://查找链表的中间结点ListNode* middleNode(ListNode* head){ListNode* fast = head;ListNode* slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;}return slow;}//反转链表ListNode* reverseList(ListNode* head){ListNode* newhead = nullptr;ListNode* cur = head;while(cur){ListNode* next = cur->next;cur->next = newhead;newhead = cur;cur = next;}return newhead;}bool chkPalindrome(ListNode* A) {// write code hereListNode* mid = middleNode(A);ListNode* head = reverseList(mid);while(head){if(A->val != head->val)return false;A = A->next;head = head->next;}return true;}
};
160. 相交链表
题目链接
思路
1.判断这两个链表是否相交。
要寻找两个链表的起始结点，首先我们需要判断这两个链表是否相交。那么如何判断两个单向链表是否相交呢？如果两个单向链表是相交的那么这两个链表的最后一个结点必定是同一个。
若两个链表的最后一个结点不是同一个结点，那么这两个链表必定不会相交。所以，我们只需判断两个链表的最后一个结点是否相同即可判断这两个链表是否相交了。
2.寻找这两个链表的起始相交结点。
我们假设这两个链表的结点个数之差为count，我们可以让指向较长链表的指针先向后移动count步，然后指向长链表的指针和指向短链表的指针再同时向后移动，这样这两个指针最后会同时走到各自的链表结尾（NULL）。
在两个指针同时向后移动的过程中，第一次指向的同一个结点便是这两个相交链表的起始结点。这时返回该结点地址即可。
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* cur1 = headA;ListNode* cur2 = headB;int lenA = 0,lenB = 0;while(cur1){lenA++;cur1 = cur1->next;}while(cur2){lenB++;cur2 = cur2->next;}if(cur1 != cur2) return NULL;ListNode* longlist = headA;ListNode* shortlist = headB;if(lenA < lenB){swap(longlist,shortlist);}int count = abs(lenA - lenB);while(count--){longlist = longlist->next;}while(shortlist != longlist){shortlist = shortlist->next;longlist = longlist->next;}return longlist;}
};