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