链表OJ练习(2)
一、分割链表
题目介绍:
思路:创建两个链表,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 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 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) { //找相遇点meetNode struct 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(lenAnext; } 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; }
还没有评论,来说两句吧...