暂时忽略特例情况
1 单链表逆置
// 利用两个指针变量存储当前节点和下一个节点的值
link h=null;//第一个节点指针域置null
while(p) //p是头指针
{
link tmp=p;//指向一个节点
p=p->next;//把p指向第二个节点
//给第一个节点指针域附值
p->next=h;
h=tmp;//存储下一个将要存储的地址
}
p=h;//赋给头指针
2 判断链表循环链接
//利用一快一慢，如果是环，则会相遇
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
return 1;
}
}
3 寻找链表中的中间元素
// 通过一个1步长，一个2步长，进行定位
while (1)
{
if (NULL == fast->next || NULL == fast->next->next)
{
return slow;
}
slow = slow->next;
fast = fast->next->next;
/* Prevent that there is a loop in the linked list. */
if (fast == slow)
{
return NULL;
}
}
4 删除链表倒数第m个元素
//两种思路：1.先计算链表长度，然后n-m，遍历二次链表
2.设置头尾两个指针，间隔m个元素，同步向前移动，当尾指针到末尾时，头指针即为所需元素
list ahead = sll;
list after = sll;
if (NULL == ahead || m <= 0)
{
return NULL;
}
while (m--)
{
if (NULL == ahead)
{
return NULL;
}
ahead = ahead->next;
if (fast && fast->next)
{
fast = fast->next->next;
if (fast == ahead)
{
return NULL;
}
}
}
while (1)
{
if (NULL == ahead)
{
return after;
}
ahead = ahead->next;
after = after->next;
if (fast && fast->next)
{
fast = fast->next->next;
if (fast == ahead)
{
return NULL;
}
}
}
5 判断一个链表部分是否是循环列表，如果是，找出其中开始相交的节点
//两种方法：1.增加一个额外数组，保留所有经过的指针，每经过一个，比较是否出现过，时间复杂度O(n),空间复杂度O(n)
2.利用两个指针，一个步长1，一个步长2，当第一次相遇的时候，另一个指针指向链表头，另一个继续，步长都为1，当相遇时刻则为交点节点处。
给出2的代码实现：
list slow = sll;
list fast = sll;
if (NULL == fast)
{
return NULL;
}
while (1)
{
if (NULL == fast->next || NULL == fast->next->next)
{
return NULL;
}
slow = slow->next;
fast = fast->next->next;
if (fast == slow)
{
slow = sll;
break;
}
}
while (1)
{
slow = slow->next;
fast = fast->next;
if (fast == slow)
{
return fast;
}
}
6 给定链表的头指针和一个结点指针，在O(1) 时间删除该结点
// 分情况，当节点是最后一个节点时，遍历删除；
如果是中间节点，找到该节点的下一个，用下一个节点覆盖要删的节点
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted)
{
if(!pListHead || !pToBeDeleted)
return;
// if pToBeDeleted is not the last node in the list
if(pToBeDeleted->m_pNext != NULL)
{
// copy data from the node next to pToBeDeleted
ListNode* pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nKey = pNext->m_nKey;
pToBeDeleted->m_pNext = pNext->m_pNext;
// delete the node next to the pToBeDeleted
delete pNext;
pNext = NULL;
}
// if pToBeDeleted is the last node in the list
else
{
// get the node prior to pToBeDeleted
ListNode* pNode = pListHead;
while(pNode->m_pNext != pToBeDeleted)
{
pNode = pNode->m_pNext;
}
// deleted pToBeDeleted
pNode->m_pNext = NULL;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}
//两种方式：1.遍历A列表，对每个A元素，与B中元素依次比较，如果相同则为，则为相交节点，时间复杂度O(m*n)
2.先得到两个列表A，B的长度，如果len（A）- len（B）=k，先A列表遍历K个元素，然后，A，B列表同步前进，当相遇的时刻，即为相交节点处。
时间复杂度：O（2（M+N））等于O（M+N）
///////////////////////////////////////////////////////////////////////
// Find the first common node in the list with head pHead1 and
// the list with head pHead2
// Input: pHead1 - the head of the first list
// pHead2 - the head of the second list
// Return: the first common node in two list. If there is no common
// nodes, return NULL
///////////////////////////////////////////////////////////////////////
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)
pFisrtCommonNode = pListHeadLong;
return pFisrtCommonNode;
}
///////////////////////////////////////////////////////////////////////
// Get the length of list with head pHead
// Input: pHead - the head of list
// Return: the length of list
///////////////////////////////////////////////////////////////////////
unsigned int ListLength(ListNode* pHead)
{
unsigned int nLength = 0;
ListNode* pNode = pHead;
while(pNode != NULL)
{
++ nLength;
pNode = pNode->m_pNext;
}
return nLength;
}