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题的解题中可以发现，快慢指针的解题思路是非常重要的，大家可以多去做一点题 ！
好了，今天的分享到这里就结束了，谢谢大家的支持！
