1.在一個排序的鏈表中，存在重復的結點，請刪除該鏈表中重復的結點，重復的結點不保留，返回鏈表頭指針
本題的意思是要刪除鏈表中重復出現的節點，然后返回刪除重復節點后的鏈表。
我們可以直接用一個哨兵位以便于觀察鏈表的情況，然后用前后指針來解決這個問題。如果當前節點cur的值與其當前節點的next的所存儲的值相等（且cur的next不為空），cur就變成cur的next，然后用while循環進行判斷，如果cur的val與cur的next的val相等且cur的next不為空，就然后cur往后移動，直到遇到不相同的情況，跳出循環后cur還要記得移動到cur的next；然后再將前指針prev的next置為cur，這樣就可以將相等的節點省略。當cur的next為空或者cur的值與cur的next的值不相等時，就直接先將prev置為cur，再將cur往后移動變成cur的next。最后返回哨兵位vpead的next，就是存儲了有效數據的首節點，就可以返回整個刪除后的單鏈表了。
完整代碼如下：
struct ListNode *deleteDuplication(struct ListNode *pHead)
{struct ListNode *vHead;vHead = (struct ListNode *)malloc(sizeof(struct ListNode));vHead->next = pHead;//定義虛頭結點方便邊界情況討論struct ListNode *pre, *cur;pre = vHead, cur = pHead;while (cur){if (cur->next && cur->val == cur->next->val){cur = cur->next;while (cur->next && cur->val == cur->next->val)cur = cur->next;//當遇到與下一節點值相同時,cur推進到最后一個重復的數字處//本數字舍去,pre連接到下一個cur = cur->next;pre->next = cur;}//遇到與下一節點值不同或者是沒有下一節點時,pre移動到此處,cur繼續后移else if(!cur->next || cur->val != cur->next->val){pre = cur;cur = cur->next;}}return vHead->next;
}
2.對鏈表進行插入排序
本題也要使用到哨兵位，用哨兵位的next最后可以返回排序完后的鏈表，并且使用前后指針，進行大小比較，若是逆序則用前后指針的關系進行交換即可
完整代碼如下：
struct ListNode *insertionSortList(struct ListNode *head)
{if (head == NULL) return head;struct ListNode *dummyHead = malloc(sizeof(struct ListNode));dummyHead->val = 0;dummyHead->next = head;//哨兵位struct ListNode *lastSorted = head;struct ListNode *curr = head->next;while (curr != NULL) {if (lastSorted->val <= curr->val) {lastSorted = lastSorted->next;} else {struct ListNode *prev = dummyHead;while (prev->next->val <= curr->val) {prev = prev->next;}lastSorted->next = curr->next;curr->next = prev->next;prev->next = curr;}curr = lastSorted->next;}return dummyHead->next;
}
3.給定一個鏈表，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 NULL
本題的意思很簡單，就是一個判斷鏈表是否有環的問題，如果有環就返回那個節點，看圖就明白了，就是最后一個節點的next會連接到前面的節點，就是有環。
到這里我們就要有一個大概的思路了–快慢指針！
我們用慢指針slow一次走一步，fast一次走兩步，到最后他們就一定會相遇，因為他們移動的差距只有一步一次追一步就必然會相遇。當slow和fast相遇時，我們再定義一個新指針從頭節點開始往后移動，同時將slow或者fast往后移動，當這個新指針與slow或者fast相等時這個節點就返回這個節點，這個節點就是鏈表尾鏈接到鏈表的節點。
完整代碼如下：
struct ListNode* detectCycle(struct ListNode* head)
{struct ListNode *slow = head, *fast = head;while (fast != NULL) {slow = slow->next;if (fast->next == NULL) {return NULL;}fast = fast->next->next;if (fast == slow) {struct ListNode* ptr = head;while (ptr != slow) {ptr = ptr->next;slow = slow->next;}return ptr;}}return NULL;
}
4.給定一個鏈表，判斷鏈表中是否有環
有了上一題的思路，這一題就很簡單了，讓slow指針和fast指針分別往后移動，slow一次走一步，fast一次走兩步，如果二者能相遇（相遇即slow指針會與fast指針相等），那就是鏈表中有環，否則無環；
完整代碼如下：
bool hasCycle(struct ListNode *head)
{struct ListNode* slow=head;struct ListNode* fast=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast)return true;}return false;
}
5.輸入兩個鏈表，找出它們的第一個公共結點
其實這一題也很簡單
首先我們得判斷這個鏈表是否會相交，如果相交，那么兩個鏈表的尾節點就會相等，若不想等就直接返回NULL指針
其次我們分別求兩個鏈表的長度，用tail尾指針遍歷求出lenA,lenB
然后我們用lenA-lenB相減的絕對值就能得出兩個鏈表的長度差gap，讓長的鏈表先走gap步，然后短的鏈表再和長的鏈表一起走，當兩個鏈表的指針節點相等時，這個節點就是兩個鏈表相遇的節點，返回這個節點即可
完整代碼如下：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{struct ListNode* tailA=headA;struct ListNode* tailB=headB;int lenA=1;int lenB=1;while(tailA){tailA=tailA->next;lenA++;}while(tailB){tailB=tailB->next;lenB++;}if(tailA!=tailB){return NULL;}int gap=abs(lenA-lenB);struct ListNode* longlist=headA;struct ListNode* shortlist=headB;if(lenA<lenB)//若長鏈表尾b則互換{longlist=headB;shortlist=headA; }while(gap--){longlist=longlist->next;}while(longlist!=shortlist){longlist=longlist->next;shortlist=shortlist->next;}return longlist;
}
我們再OJ題的解題中可以發現，快慢指針的解題思路是非常重要的，大家可以多去做一點題 ！
好了，今天的分享到這里就結束了，謝謝大家的支持！
】)
