growing
分类： C/C++
2015-11-17 12:13:30
1.比较顺序表和链表的优缺点，说说它们分别在什么场景下使用？
链表：
{
缺点：需要多余的空间存储指针。
存取某个元素速度慢，需要遍历。
优点：插入元素和删除元素速度快。
没有空间限制,存储元素的个数无上限,基本只与内存空间大小有关
}
顺序表：
{
优点：空间利用率高。
存取某个元素速度快（直接靠下标即可）
缺点：插入元素和删除元素存在元素移动,速度慢,耗时。
有空间限制,当需要存取的元素个数可能多于顺序表的元素个数时,会出现"溢出"问题.当元素个数远少于预先分配的空间时,空间浪费巨大.
}
总结：频繁的插入、删除数据时应用链表。
2.从尾到头打印单链表
void PrintReverse(ListNode *pHead)
{
if(pHead)
{
if(pHead->next)
{
PrintReverse(pHead->next);
}
printf("%d->",pHead->data);
}
}
3.删除一个不给头单链表的非尾结点
void DelNonTailNode(ListNode* pos)
{
assert(pos && pos->_next);
pos->_data = pos->_next->_data;
ListNode* next = pos->_next->_next;
free(pos->_next);
pos->_next = next;
}
思路：把要删除的结点后一个结点的值赋给此结点，再删除它后面的结点即可。
4.在不给头单链表的一个非头结点前插入一个结点
void InsertFrontNode(ListNode* pos, DataType x)
{
assert(pos);
ListNode* tmp = BuyNode(x);
tmp->_next = pos->_next;
pos->_next = tmp;
DataType tmpData = tmp->_data;
tmp->_data = pos->_data;
pos->_data = tmpData;
}
思路：因为不给头所以只能插在所给位置的后面，所以插在先所给位置的后面，然后再和前面结点的值交换即可。
5.单链表实现约瑟夫环
ListNode *JosephCycle(ListNode *pHead,int x)
{
if(pHead == NULL)
{
printf("nothing in list");
return NULL;
}
ListNode *cur = pHead;
//成环
while(cur->next != NULL)
{
cur = cur->next;
}
cur->next = pHead;
// 开始删
cur = pHead;
while(1)
{
if(cur->next != cur)
{
int count = x;
while(--count)
{
cur = cur->next;
}
//想删cur，由于没有定义cur的前驱结点，所以将cur下一个结点的值赋给cur，再删下一个结点即可
cur->data = cur->next->data;
ListNode *tmp = cur->next;
cur->next = cur->next->next;
free(tmp);
}
else
{
cur->next = NULL;//解环，免得打印的时候停不下来。
return cur;
}
}
}
6.逆置单链表
ListNode *Reverse(ListNode *&pHead)
{
ListNode *newHead = NULL,*cur = pHead;
while(cur)
{
ListNode* tmp = cur;
cur = cur->next;
tmp->next = newHead;
newHead = tmp;
}
return newHead;
}
思路：从头到尾每摘下来一个结点，就连在新的newhead上，最后返回newhead即可。
7.单链表排序（冒泡，快排）vo
id Bubblesort(ListNode *pHead)
{
if(pHead == NULL || pHead->next == NULL)
{
printf("cant sort!\n");
return;
}
ListNode *cur = pHead->next,*prev = pHead,*tail = NULL;
int flag;
while(tail != pHead)
{
while(cur != tail)
{
if(prev->data > cur->data)
{
DataType tmp = prev->data;
prev->data = cur->data;
cur->data = tmp;
flag = 1;
}
prev = cur;
cur = cur->next;
}
if(flag = 0)
{
return;
}
tail = prev;
cur = pHead->next;
prev = pHead;
flag = 0;
}
return;
}
8.合并两个有序链表，合并完依然有序。
ListNode *MergeList(ListNode *pHead1,ListNode* pHead2)
{
ListNode *cur1 = pHead1,*cur2 = pHead2;
ListNode *newHead = BuyNode(0);
ListNode *cur = newHead;
if((pHead1 == NULL) && (pHead2 == NULL))
{
printf("two empty list\n");
return NULL;
}
else if(pHead1 == NULL)
{
return pHead2;
}
else if(pHead2 == NULL)
{
return pHead1;
}
while(cur1 && cur2)
{
if(cur1->data < cur2->data)
{
cur->next = cur1;
cur = cur->next;
cur1 = cur1->next;
}
else
{
cur->next = cur2;
cur2 = cur2->next;
cur = cur->next;
}
}
cur->next = (cur1 != NULL)?cur1:cur2;
ListNode* tmp = newHead;
newHead = newHead->next;
free(tmp);
return newHead;
}
9.查找单链表的中间结点，要求只能遍历一次。
ListNode* FindMid(ListNode* pHead)
{
ListNode* slow = pHead, *fast = pHead;
//
while (fast && fast->_next)
{
slow = slow->_next;
fast = fast->_next->_next;
}
return slow;
}
思路：定义两个指针，一个一次走两步，一个一次走一步，当快的走到了终点，慢的即在中间了。
10.查找单链表的倒数第K个结点，要求只能遍历一次。
ListNode* FindTailnNode(ListNode* pHead,int k)
{
ListNode *fast = pHead;
ListNode* slow =pHead;
while(--k)
{
if(fast->next != NULL)
{
fast = fast->next;
}
else
{
printf("dont have this node/n");
return NULL;
}
}
while(fast->next != NULL)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}思
路：定义两个指针，一个走了K步之后，两个一起走，前面的到达了终点，后面那个自然就是倒数第K个。
11.判断单链表是否带环？若带环，求环的长度、入口点。并计算每个算法的时间复杂度&空间复杂度；
(1).判断链表是否有环
bool IsLoop(ListNode *pHead)
{
ListNode *fast = pHead,*slow = pHead;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
return true;
}
}
return false;
}
思路：设置两个遍历指针，第一个每次走两步，第二个每次走一步，这样如果两个指针能相遇则说明链表有环。
(2).求环长
ListNode *IsLoop(ListNode *pHead)//返回快慢指针的相遇点
{
ListNode *fast = pHead,*slow = pHead;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
return slow;
}
}
return NULL;
}
int Cyclelength(ListNode *pHead,ListNode *meet)
{
ListNode *cur = meet;
int count = 0;
while(cur->next != meet)
{
cur = cur->next;
count++;
}
return count;
}
思路：接着第一问，记录出两个指针在环中相遇的地点，从这个地点再遍历一遍环即可求出环长。
（3）求入口
第一种方法：
ListNode *CycleEnter(ListNode *pHead,ListNode *meet)
{
ListNode *cur1 = pHead,*cur2 = meet;
while(cur1 != cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}
思路：
fast:L+nC+X
slow:L+X
fast为slow的两倍，解方程就知道 L = nC - X
第二种方法：
/*ListNode *CycleEnter(ListNode *pHead,int len)
{
ListNode *fast = pHead,*slow = pHead;
int count = len;
while(count--)
{
fast = fast->next;
}
while(slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}*/
思路：
快指针先走环的长度，它们再一起走，相遇的地点就是入口。慢指针到那里的时候，快指针刚好把环走了一圈。
12.判断两个链表是否相交，若相交，求交点。（假设链表不带环）
（1）.判断是否相交（不带环）
bool IsIntersect(ListNode *pHead1,ListNode* pHead2)
{
ListNode *fast = pHead1,*slow = pHead2;
if((fast == NULL) || (slow == NULL))
{
return false;
}
while(fast->next)
{
fast = fast->next;
}
while(slow->next)
{
slow = slow->next;
}
if(fast == slow)
{
return true;
}
return false;
}
思路：
如果相交即是两个链表尾部相交，则两条链表的最后一个节点肯定相同。因此，只要判断两条链表的最后一个节点是不是相同就可以了。这种方法只需要遍历一遍每个链表找到它们的最终节点就可以了，所以算法的复杂度为O（n）。
但如果是带环的就不行了，因为找不到尾结点。
（2）求交点
ListNode *EnterCross(ListNode *pHead1,ListNode* pHead2)
{
ListNode *cur1 = pHead1,*cur2 = pHead2;
int len1 = 0,len2 = 0;
//?ó????????±í???¤??
while(cur1->next != NULL )
{
cur1 = cur1->next;
len1++;
}
while(cur2->next != NULL )
{
cur2 = cur2->next;
len2++;
}
if(len1 > len2)
{
int x = len1 - len2;
ListNode *fast = pHead1,*slow = pHead2;
while(x--)
{
fast = fast->next;
}
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
else if(len1 < len2)
{
int x = len2 - len1;
ListNode *fast = pHead2,*slow = pHead1;
while(x--)
{
fast = fast->next;
}
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
else
{
ListNode *fast = pHead1,*slow = pHead2;
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
思路：
如果相交，则交点之后的链表节点同时属于这两个链表。由此可以推断出，交点之后每条链表上节点的个数肯定是相同的。因此，如果两条链表节点的个数分别为len1和len2(len1>len2)，那么他们的第一个交点在第一条链表上肯定是第(len1-len2)个节点之后的某个节点。
总结上面的分析，我们得出一算法：
1.先分别遍历一遍两条链表，求出两链表各自的节点个数len1和len2。
2.让节点多的链表先走|len1-len2|
3.两条链表同时向后步进，并判断节点是否相同。第一个相同点就是第一个交点。
13.判断两个链表是否相交，若相交，求交点。（假设链表可能带环）
(1).判断是否相交
bool TwocyleIsLoop(ListNode *pHead1,ListNode* pHead2)
{
while(IsLoop(pHead1) && IsLoop(pHead2))
{
ListNode *fast = pHead1,*slow = pHead2;
while(fast != slow)
{
fast = fast->next->next;
slow = slow->next;
}
return true;
}
}
若是死循环就是不带环的（各自在各自环里跑），若是返回TURE就是带环的。
（2）求交点
首先有两种交法。
第一种：先用已经写过的函数求出环的长度和环的入口，然后分别让两个指针分别从两个链表的头部，一遍走一遍计数走到入口然后再走环的长度，这样就可以求出两条指针的长度了，就转化成了第12题的第2问。
第二种：两个链表进去的交点是不一样的。直接各自求就可以了。
14.复制一个复杂单链表。（剑指offer）
点击(此处)折叠或打开
