单链表的扩展操作21----legend050709

标签：链表 slow 21 legend050709 fast next ---- pnode 节点

单链表的操作之补充：

(1). 单链表的反转：

(2). 单链表的排序（插入排序，选择排序，冒泡排序等）：

(3). 单链表取得最小值的节点，及其前驱：

(4). 单链表获取最小的k个节点：

（4-1）单链表的中间节点：

(5).单链表节点的追赶问题：

(6). 两个链表公共节点：

(7).单链表是否有环：

(8)两链表的交集，并集之 2路归并问题：

-------------------------------------------------------------------------------------------

(1). 单链表的反转：

/*带有头节点的单链表的反转
思想: 想让整个链表反转，先将两个节点反转，然后节点的追赶。
 
本来是pnode1->pnode2->pnode3..
然后  逆序为pnode1<-pnode2...
然后         更新pnode1为pnode2;
           更新pnode2为pnode3;(即链表中节点的追赶)
*/
void reverse(LINKLIST linklist){
 
     if(NULL==linklist->next->next || NULL==linklist->next)
     {
           printf("单链表头节点后只有一个节点，或者只有一个头节点，不需要反转\n");
           return ;
     }
 
     NODEPTR pnode1=linklist->next;/*第一个节点*/
     NODEPTR pnode2=pnode1->next;/*第二个节点*/
 
     pnode1->next=NULL;/*第一个节点变成了尾节点*/
 
     NODEPTR pnode3;
     while(pnode2){
     pnode3=pnode2->next;
 
     pnode2->next=pnode1;
 
     pnode1=pnode2;
     pnode2=pnode3;
     }
     /*
     节点的追赶，由于pnode1,pnode2只相差一个节点，所以循环结束时pnode2为null，
     pnode1为之前的尾节点。
     */
 
     linklist->next=pnode1;
 
}

(2). 单链表的排序（插入排序，选择排序，冒泡排序等）：

(2.1).选择排序：

/*与数组的选择排序类似，每次选择出最小的元素放到新的数组中。*/
         /*LINKLIST  ，NODEPTR 是 NODE* 类型的 */
      NODEPTR selectAscentSort(LINKLIST linklist){
 
     NODEPTR pnode=linklist->next;
 
 
     LINKLIST newLinklist;
     initLinkList(&newLinklist);
         /*initLinkList函数是为 了建立一个有头结点的空链表*/
 
     NODEPTR newPNode=newLinklist->next;
 
     NODEPTR pMinmumNode,pPreMinmum;
 
     while(pnode){
     pMinmumNode=minmumNode(linklist,&pPreMinmum);
 
           if(pMinmumNode){
           pPreMinmum->next=pMinmumNode->next;
         //从原有的链表中取掉最小的节点pMinmunNode。
        
         //头插法建立新的链表，不断更新头。
           pMinmumNode->next=newPNode;
           newLinklist->next=pMinmumNode;
           newPNode=pMinmumNode;
 
           pnode=pnode->next;
           }
     }
return newLinklist;
 
}

（2.2）插入排序：

/*思想：类似于数组的插入排序，从第2个元素开始往后，将元素逐个插入到前面已经有序的
数组中*/
 
void insertSort(LINKLIST linklist){
 
 
     if(linklist->next)
      {
     NODEPTR pnode_oldList=linklist->next->next;
     /*旧链表从第二个节点开始。*/
     NODEPTR pNode_newList=linklist->next;
     NODEPTR pre_pPnode_newList=linklist;
     pNode_newList->next=NULL;
     NODEPTR pTempNode;
     /*初始时newlist中除了头节点，只有一个节点，就是第一个节点*/
 
     while(pnode_oldList){
 
           NODEPTR pNode_newList=linklist->next;
           NODEPTR pre_pPnode_newList=linklist;
           // 从小到大排序
           while(pNode_newList &&pnode_oldList->data>pNode_newList->data){
            pre_pPnode_newList=pNode_newList;
           pNode_newList=pNode_newList->next;
           }
           /*

此中注意：空节点的处理，如果原链表中有空节点，则插入一个节点之后还是有空节点的，即使是插在最后一个节点之后。

因为之后一个节点的next为NULL，即NULL 的前驱为最后一个节点，即使是一个节点插在最后一个节点之后，

那么NULL 还是会有的。

所以，链表初始化的时候必须给尾节点的next置为NULL。

*/
           /*插入节点*/
           /*注意此中如果pnode_oldList=pnode_oldList->next的位置放在下面注释中，
           则出错，因为在那之前pnode_oldList已经改变了*/
           pTempNode=pnode_oldList;
 
           pnode_oldList=pnode_oldList->next;
 
           pTempNode->next=pNode_newList;
           pre_pPnode_newList->next=pTempNode;
 
           /*pnode_oldList=pnode_oldList->next;*/
     }
 
     }
 
 
}

(3). 单链表取得最小值的节点，及其前驱：

NODEPTR minmumNode(LINKLIST linklist,NODEPTR * preNode){
 
     NODEPTR pnode;
 
     if(linklist->next){
 
     NODEPTR p_minNode=linklist->next;
     *preNode=linklist;
 
           for(pnode=linklist;pnode->next!=NULL;pnode=pnode->next){
                 if(pnode->next->data<p_minNode->data){
                  *preNode=pnode;
                  p_minNode=pnode->next;
 
                  }
           }
 
           return p_minNode;
     }
 
     return NULL;
 
}

(4). 单链表获取最小的k个节点：

（4.1）思路一：类似于选择排序中每次获取最小的一个节点，连续获取k次即可。

（4.2）思路二：构建最大堆。

(5).单链表的追赶问题：

(5.1)求链表的倒数第k个节点：

思想：：设置两个指针p1,p2，首先p1和p2 都指向head，然后p2 向前走k 步，这样p1 和p2 之间就间隔k 个节点，最后p1 和p2 同时向前移动，直至p2 走到链表末尾。

（5-2）链表的中间节点：

链表的中间节点：
（1）方法一：
遍历一遍，求出长度len，然后在遍历len/2个长度；
（2）方法二：（推荐）
两个速度不一致的指针：
一个指针一次走一个节点，另一个指针一次走两个节点。

总结：
链表的追赶问题，一般的解法都是
1）两个指针，一个走的快，一个走的慢；

2）两个指针，一个先走，一个后走；

(6).两个单链表相交：

(6.1)两个单链表是否相交：

（0）图解：带环相交与不带环相交

单链表的扩展操作21----legend050709_链表

单链表的扩展操作21----legend050709_链表_02

分析：两个单链表相交，要么交于尾节点这一个节点，

要么有多个相交点。

因为：假设两个链表只交于中间的某一个节点，该节点后面节点不相交，那么

这个节点就会有两个next.显然不对。

总结：如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的。

（1）思路一：直接判断list1中的每个节点是否在list2中 .O(n1*n2) :

n1为list1的节点数；

。。。

（2）思路二：hashTable，时间复杂度O(n1+n2),

空间复杂度O(n1) :

针对第一个链表直接构造hash表，然后查询hash 表，判断第二个链表的每个结点是否在hash 表出现，如果第二个链表的结点在hash表中找到，即说明第二个链表与第一个链表有相同的结点。时间复杂度为为线性,

O(n1+n2)同时为了存储第一个链表的所有节点，空间复杂度为O(n1);

（3）思路三：

时间复杂度O(n1+n2);空间复杂度为O(1);

考虑“如果两个没有环的链表相交于某一节点，那么在这个节点之后的所有节点都是两个链表共有的”这个特点，我们可以知道，如果它们相交，则最后一个节点一定是共有的。

所以，先遍历第一个链表，记住最后一个节点。然后遍历第二个链表，到最后一个节点时和第一个链表的最后一个节点做比较，如果相同，则相交，否则，不相交。

总结：两个链表是否相交：

1.先判断带不带环

2.如果都不带环，就判断尾节点是否相等

3.如果都带环，判断一链表上俩指针相遇的那个节点，在不在另一条链表上。

如果在，则相交，如果不在，则不相交。

代码实现：

/*
1.如果都不带环，就判断尾节点是否相等
2.如果都带环，判断一链表上俩指针相遇的那个节点，
在不在另一条链表上。
*/
bool isIntersected(Node * head1, Node *head2)
{
Node * circleNode1;
Node * circleNode2;
Node * lastNode1;
Node * lastNode2;
bool isCircle1 =isCircle(head1,circleNode1, lastNode1);
bool isCircle2 =isCircle(head2,circleNode2, lastNode2);
//一个有环，一个无环
if(isCircle1 != isCircle2)
return false;
//两个都无环，判断最后一个节点是否相等
else if(!isCircle1 && !isCircle2)
return lastNode1 == lastNode2;
}
//两个都有环，判断环里的节点是否能到达另一个链表环里的节点
else
{
Node * temp = circleNode1->next;
 /*updated*/
while(temp != circleNode1)
{
if(temp == circleNode2)
return true;
temp = temp->next;
}
return false;
}
return false;
}

（6.2）求两个链表相交的第一个节点：

单链表的扩展操作21----legend050709_单链表操作补充_03

（1）思路：顺序遍历两个链表到尾结点的时候，我们不能保证在两个链表上同时到达尾结点。这是因为两个链表不一定长度一样。但如果假设一个链表比另一个长L 个结点，我们先在长的链表上遍历L个结点，之后再同步遍历，这个时候我们就能保证同时到达最后一个结点了。由于两个链表从第一个公共结点开始到链表的尾结点，这一部分是重合的。因此，它们肯定也是同时到达第一公共结点的。于是在遍历中，第一个相同的结点就是第一个公共的结点。

（2）步骤：

1.两个链表的长度len1，len2；

2、在长的链表上先遍历len2-len1之后，再同步遍历两个链表，直到找到相同的结点，或者一直到链表结束。

（3）代码如下：

ListNode* FindFirstCommonNode( ListNode*pHead1, ListNode *pHead2)
{
// Get the length of two lists
unsigned int nLength1 = ListLength(pHead1);
unsigned int nLength2 = ListLength(pHead2);
int nLengthDif = nLength1 - nLength2;
// Get the longer list
ListNode *pListHeadLong = pHead1;
ListNode *pListHeadShort = pHead2;
if(nLength2 > nLength1)
{
pListHeadLong = pHead2;
pListHeadShort = pHead1;
nLengthDif = nLength2 - nLength1;
}
 
// Move on the longer list
for(int i = 0; i < nLengthDif; ++ i)
pListHeadLong = pListHeadLong->m_pNext;
// Move on both lists
while((pListHeadLong != NULL) &&(pListHeadShort != NULL) && (pListHeadLong !
= pListHeadShort))
{
pListHeadLong = pListHeadLong->m_pNext;
pListHeadShort =pListHeadShort->m_pNext;
}
// Get the first common node in two lists
ListNode *pFisrtCommonNode = NULL;
if(pListHeadLong == pListHeadShort&& pListHeadLong !=NULL)
pFisrtCommonNode = pListHeadLong;
return pFisrtCommonNode;
}

(7).单链表是否有环：

(7.1)单链表是否有环：

（1）图解：

单链表的扩展操作21----legend050709_ci_04

（2）思路：设置两个指针(p1, p2)，初始值都指向头，

p1 每次前进一步，p2 每次前进二步，如果链表存在环，则p2 先进入环，p1 后进入环，两个指针在环中走动，必定相遇。

（3）代码实现：

/*判断是否带环，如果有环则返回true,并且得到环中的一个节点cycleNode，

如果没有环则得到最后一个节点;

用两个指针，一个指针步长为1，

一个指针步长为2，判断链表是否有环*/

bool isCircle(Node * head, Node *&circleNode, Node *& lastNode)
{
Node * fast = head->next;
Node * slow = head;
while(fast != slow && fast&& slow)
{
 
if(fast->next != NULL)
fast = fast->next;
 
if(fast->next == NULL)
lastNode = fast;
 
if(slow->next == NULL)
lastNode = slow;
 
/*此句是否可以不要？因为如果无环，一定是fast先到结尾。
如果有环，则不存在lastnode;
*/
 
fast = fast->next;
slow = slow->next;
 
}
if(fast == slow && fast &&slow)
{
circleNode = fast;
return true;
}
else
return false;
}

（7.2）寻找环的入口点：

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了step步，（step是从起点开始算起的）则fast走了2step步（fast步数还等于s 加上在环上多转的n圈），设环长为cycleLen，则：

2step= step + n*cycleLen;

所以step=n*cycleLen;

假设整个链表长为len,入口环与相遇点距离为ruyu;

起点与环入口点距离为ruqi;

则ruqi+ruyu+m*cycleLen=step=n*cycleLen;

所以定义ruqi+ruyu=k*cycleLen;

(k=n-m)

ruqi+ruyu=(k-1)cycleLen+cycleLen

=(k-1)cycleLen+len-ruqi;

所以：ruqi=(k-1)cycleLen+(len-ruqi-ruyu);

len-ruqi-ruyu即为相遇点到环入口点的距离；

所以：从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

所以代码如下：

Node* FindLoopPort(Node *head)
{
   Node *slow = head, *fast = head;
 
   while ( fast && fast->next )
    {
       slow = slow->next;
       fast = fast->next->next;
       if ( slow == fast ) break;
    }
 
   if (fast == NULL || fast->next == NULL)
       return NULL;
       /*
       此时 slow=fast=相交点
       */
   slow = head;
   while (slow != fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
 
   return slow;
}

(8).两链表的交集，并集之 2路归并问题：

类似于线性表中，先排序，然后处理。

==========================

链表的操作总结：
（1）链表的反转；
（2）链表的两个指针的追赶问题；
比如链表是否有环；获取倒数第k个节点；获取链表的中间节点；

（3）获取链表长度 + 一链表指针先走问题；
比如获取两个链表的第一个相交节点；

（4）两个有序链表的合并；

标签：链表,slow,21,legend050709,fast,next,----,pnode,节点
From： https://blog.51cto.com/u_15911260/5934925

单链表的扩展操作21----legend050709

相关文章

赞助商

阅读排行