1.可以通过记录最后一个节点来判断是否相交
| while(pa->next)
{
????pa = pa-next;
}?
while(pb->next)
{
????pb= pb->next;
}
if(pa == pb){...}
|
2.只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点，无头结点
基本原理，讲当前结点的下个一个结点的数据赋值给当前结点，然后释放下一个结点。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | typedef?struct?node
{
????int?value;
????struct?node *next;
} list_node;
void?test(list_node* pCur)
{
????list_node *pNext = pCur->next;
????if?(pNext)
????{
????????pCur->next = pNext->next;
????????pCur->value = pNext->value;
????}
????delete?pNext;
}
|
3.给定一个结点指针，在结点之前插入一个结点，解法同上
先后插一个结点，然后交换当前结点和后面结点的数据。?
4.判断单链表是否有环
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | typedef?struct?node
{
????int?value;
????struct?node *next;
} list_node;
int???is_link_list_cicled(list_node*?? head)?????
{?????
????list_node *p = head,??
????list_node *q = head;?????
????while(p && q)?????
????{?????????????????????????
????????p =? p-> next;?????
????????q =? q-> next;?????
????????if(!q)?????
????????????return?0;?????
????????q = q-> next;???????
????????if(!q)?????
????????????return?0;?
?????????if(p?? ==?? q)?????
????????????return???1;??
????}
}
|
?5.找到环的入口点
公式x = （n-1）y + y -d;
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | typedef?struct?node
{
????int?value;
????struct?node *next;
} list_node;
int???is_link_list_cicled(list_node*?? head)?????
{?????
????list_node *slow = head,??
????list_node *fast = head;?????
????while(slow && fast)?????
????{?????????????????????????
????????slow =? slow-> next;?????
????????fast =? fast-> next;?????
????????if(!fast)?????
????????????return?0;?????
????????fast = fast-> next;?????
????????if(!fast)?????
????????????return?0;?
?????????if(slow?? ==?? fast)?????
????????????return???break;??
????}
//找到换的入口点
????while(slow != fast)
????{
????????slow = slow->next;
????????fast = fast->next;
????}
}
|
6.找出倒数第k个数
原理：使用两个指针相差k-1，当第一个指针指向最后的时候，第二个指针则指向第K个位置
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | list_node*?? findK(list_node*?? head,int?k)?????
{?????
????list_node* pAhead = head->next;
????list_node* pbehind = head->next;
????for?(int?i = 0;i < k ;++i)
????{
????????pAhead = pAhead->next;
????}
????while(pAhead->next)
????{
????????pAhead = pAhead->next;
????????pbehind = pbehind->next;
????}
????return?pAhead;
}
|
7.若结点个数为奇数则返回中间结点
若为偶数则返回中间第一个个结点
| while(p->next && p->next->next)
{
??q = q->next;
??p = p->next->next;
}
return?q;
|
?8.带头结点的链表转置
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | list_node*?? findK(list_node*?? head)?????
{?????
????list_node* pPrev =NULL;
????list_node* pCur = head->next;
????list_node* pNext = NULL;
????while(pCur)
????{
????????pNext = pCur;
????????pCur->next = pPrev;
????????pPrev = pCur;
????????pCur = pNext;
????}
????head->next = pPrev;
????return?NULL;
}
|
9.找出相交链表的交点
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | list_node*?? findK(list_node*?? heada,list_node *headb)?????
{?
????list_node *p = heada->next;
????list_node *q = headb->next;
????int?pLen = 0;
????int?qLen = 0;
????int?steps =?abs(pLen -qLen);
????list_node *head = pLen > qLen? p:q;
????while(steps)
????{
????????head = head->next;
????????steps--;
????}
????pLen>qLen?p = head:q=head;
????while(p!=q)
????{
????????p = p->next;
????????q = q->next;
????}
????return?NULL;
}
|