注意：数据结构画图和调试非常重要
CM11 链表分割
比如 1 2 7 4 8 3 9 x=4
输出：1 2 3 4 7 8 9(相对位置不变)
思路：把小于的连在一起，再把大于等于的连在一起，再都连在一起
class Partition { public: ListNode* partition(ListNode* pHead, int x) { // write code here ListNode* tail1=NULL; ListNode* head1=NULL; ListNode* tail2=NULL; ListNode* head2=NULL; ListNode* cur=pHead; ListNode* next=pHead; while(next!=NULL) { if(cur->val<x) { next=cur->next; if(head1==NULL) { head1=cur; tail1=cur; tail1->next=NULL; cur=next; } else { tail1->next=cur; tail1=cur; tail1->next=NULL; cur=next; } } else { next=cur->next; if(head2==NULL) { head2=cur; tail2=cur; tail2->next=NULL; cur=next; } else { tail2->next=cur; tail2=cur; tail2->next=NULL; cur=next; } } } if(tail1==NULL) { return head2; } else if(tail2==NULL) { return head1; } else { tail1->next=head2; } return head1; } };
OR36 链表的回文结构
比如： 1 2 3 2 1就是回文结构 或者 1 2 2 1这样。
思路：先找到中间节点，再后半部分逆置，再逐个比较。
class PalindromeList { public: bool chkPalindrome(ListNode* A) { if (A == NULL || A->next == NULL) return true; ListNode* slow, *fast, *prev, *cur, *nxt; slow = fast = A; //找到中间节点 while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } prev = NULL; //后半部分逆置 cur = slow; while (cur) { nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } //逐点比对 while (A && prev) { if (A->val != prev->val) return false; A = A->next; prev = prev->next; } return true; } };
