链表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 < 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;
}