一、分割链表
题目介绍:
思路:创建两个链表,ghead尾插大于x的节点,lhead尾插小于x的节点。先遍历链表。最后将ghead尾插到lhead后面,将大小链表链接。
我们需要在创建两个链表指针,指向两个链表的头节点,用这两个指针标记lhead和ghead的尾结点,方便与尾插。
注:极端边界场景:所有值都小于x; 所有值都大于x; 空链表。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/class Partition {
public:ListNode* partition(ListNode* pHead, int x){ListNode* gtail, * ghead, * ltail, * lhead;gtail = ghead = (struct ListNode*)malloc(sizeof(struct ListNode));ltail = lhead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = pHead;while (cur){if (cur->val < x){ltail->next = cur;ltail = ltail->next;}else{gtail->next = cur;gtail = gtail->next;}cur = cur->next;}ltail->next = ghead->next;gtail->next = NULL;struct ListNode* newhead = lhead->next;free(lhead);free(ghead);return newhead;}
};
二、回文链表
题目介绍:
思路:先找到中间节点,可以利用快慢指针找到中间节点,然后将中间节点后面的节点翻转,在和中间节点前面的链表依次比较,如果全部相同则是回文链表否则不是。
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
//struct ListNode* middleNode(struct ListNode* head)
{struct ListNode* falst;struct ListNode* slow;falst = head;slow = head;while (falst && falst->next){slow = slow->next;falst = falst->next->next;}return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{struct ListNode* cur = head;struct ListNode* newhead = NULL;while (cur){struct ListNode* next = cur->next;//头插cur->next = newhead;newhead = cur;cur = next;}return newhead;
}class PalindromeList
{
public:bool chkPalindrome(ListNode* head){//找到中间节点,将中间节点后面的链表翻转,有第一个和中间节点比较,并依次后移,若全部相同,则为回文链表,反之不是。struct ListNode* mid = middleNode(head);struct ListNode* rmid = reverseList(mid);while (rmid && mid){if (rmid->val != head->val){return false;}head = head->next;rmid = rmid->next;}return true;}};
三、找公共点
题目介绍:
思路:先遍历两个链表,计算出两个链表的长度,让后计算出两个链表的长度差k,将长的链表先往前走k步,然后将两个链表指针同时后移,找到第一个相同的节点就是相交节点。
注:需要考虑到空链表,给链表判空,若空headA和headB其中一个为空返回NULL。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* curA = headA;struct ListNode* curB = headB;int lenA = 1;int lenB = 1;if(headA==NULL||headB==NULL){return NULL;}while (curA->next){curA = curA->next;lenA++;}while (curB->next){curB = curB->next;lenB++;}if (curA != curB) //没有交点{return false;}int gap = abs(lenA - lenB);struct ListNode* falst = headA;struct ListNode* slow = headB;if (lenA < lenB){falst = headB;slow = headA;}while (gap--){falst = falst->next;}while (slow != falst){slow = slow->next;falst = falst->next;}return slow;
}
四、判断是否是环形链表
题目介绍:
思路:还是利用快慢指针,当慢指针往前走一步,快指针往前走两步,在一个环中,每次他们的距离就减少一,如果有环,就一定能追上。如果没追上则没有环。
用快指针遍历。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head)
{struct ListNode *falst=head;struct ListNode *slow=head;while(falst&&falst->next){falst=falst->next->next;slow=slow->next;if(falst==slow){return true;}}return false;
}
五、寻找环形链表的入环节点
题目描述:
思路1:假设链表带环,头节点head与入环节点的距离为L,入环节点与相遇点的距离为D,环的大小为C,如下图:
fast从头节点到相遇点:L + D + kC,其中k为正整数,表示在快慢指针相遇前fast所走圈数
slow从头节点到相遇点:L + D
又由于fast每次走两步,slow每次走一步,以上二式可以建立起联系:
L + D + kC = 2 * (L + D)
L = kC - D = (k - 1) * C + C - D
所以可以得出结论:一个指针从相遇点开始走,一个指针从链表头开始走,则这两个指针一定会在入环节点处相遇。
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast=head, *slow=head;while(fast && fast->next){fast=fast->next->next;slow = slow->next;if(fast == slow){//找相遇点meetNodestruct ListNode* meetNode = fast;//相遇点可能就是入环节点if(meetNode == head)return head;//meetNode和head开始每次走一步,直到相遇while(head && meetNode){meetNode = meetNode->next;head = head->next;//当相遇时即为入环节点if(meetNode == head)return meetNode;}}}return NULL;
}
思路2:我们可以在相遇点将链表断开,找到如节点就相当于找到两个链表的交点。
找两个链表的交点我们可以参考题目三
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode *curA=headA;struct ListNode *curB=headB;int lenA=1;int lenB=1;while(curA->next){curA=curA->next;lenA++;}while(curB->next){curB=curB->next;lenB++;}if(curA!=curB) //没有交点{return false;}int gap=abs(lenA-lenB);struct ListNode *falst=headA;struct ListNode *slow=headB;if(lenA<lenB){falst=headB;slow=headA;}while(gap--){falst=falst->next;}while(slow!=falst){slow=slow->next;falst=falst->next;}return slow;
}
struct ListNode *detectCycle(struct ListNode *head)
{struct ListNode *fast=head;struct ListNode *slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast) //相遇了{struct ListNode *meet=slow; //将环断开struct ListNode *newhead=meet->next;meet->next=NULL;return getIntersectionNode(head,newhead); //找两个链表的交点}}return NULL;
}