关于链表
链表是一种动态的数据结构，因为在创建链表时无需知道链表的长度，当插入一个节点时，只需要为新的节点分配内存，其空间效率和数组相比要高，但是每次都要创建空间所以时间不是很高
单向链表定义节点
struct ListNode
{
int m_value;
ListNode* m_pNext;
};在链表后面添加节点
void AddToTail(ListNode** pHead,int value)//时间效率O(N)
{
ListNode* pnewNode=new ListNode();//创建新结点
pnewNode->m_value=value;
pnewNode->m_pNext=NULL;
if(pHead==NULL)//当头结点为空
{
pHead=pnewNode;
}
else//不为空
{
ListNode*pNode=*pHead;
while(pNode->m_next!=NULL)//遍历找到最后一个节点
{
pNode=pNode->m_next;
}
pNode->m_next=pnewNode;
}
}删除其中某节点
void RemoveNode(ListNode**pHead, int value)
{
if (pHead == NULL||*pHead==NULL)//头结点为空
return;
ListNode*pDelete = NULL;
if ((*pHead)->m_value == value)
{
pDelete = *pHead;
*pHead = (*pHead)->m_pNext;
}
else
{
ListNode*pNode = *pHead;
//遍历查找要删除结点的前一个结点
while (pNode->m_pNext!=NULL &&pNode->m_pNext-> m_value != value)
{
pNode = pNode->m_pNext;
}
pDelete = pNode->m_pNext;
pNode->m_pNext = pDelete->m_pNext;
if (pDelete != NULL)
{
delete pDelete;
pDelete = NULL;
}
}题目1：
输入一个链表头结点，从头到尾反过来打印这个结点值（不改变结点结构）
程序1.0
若链表为空直接返回链表，若只有一个节点，打印此结点；若有多个结点，设置一个计数器，先、遍历结点统计结点个数，再循环结点数次，在这个循环里再依次找到倒数第一个、倒数第二个、倒数第N个节点
void PrintListReverse(ListNode*pHead)//时间复杂度O（N^2）
{
while (pHead == NULL)//没有结点
return;
if (pHead->m_pNext == NULL)//一个节点
{
cout << pHead->m_value;
return;
}
ListNode*pNode = pHead;
int count =1;
while (pNode->m_pNext != NULL)
{
count++;
pNode = pNode->m_pNext;
}
while (count != 0)
{
for (int i = 1; i < count; i++)
{
pNode = pNode->m_pNext;//找到倒数第N个节点的前一个结点
}
cout << pNode->m_value << "->";
count--;
}
}程序2.0
上面用循环实现，过于复杂且效率不高，所以第二次使用栈来完成，栈有“先入后出”的特性，所以用栈来实现更为方便，没遇到一个不为空的结点就把它放到栈中
void PrintListReverse(ListNode*pHead)//时间复杂度O(N)
{
stack s1;
ListNode*pNode = pHead;
while (pNode->m_pNext != NULL)
{
s1.push(pNode);
pNode = pNode->m_pNext;
}
while (!s1.empty())
{
cout << s1.top()->m_value << "->";
s1.pop();
}
} 程序3.0
我们知道递归的本质就是栈，所以我们也可以用栈来实现它，先递归后面的结点，一直递归到没有结点，再输出该结点
void PrintListReverse(ListNode*pHead)
{
if (pHead != NULL)
{
if (pHead->m_pNext != NULL)//递归停止条件
{
PrintListReverse(pHead->m_pNext);
}
cout << pHead->m_value << "->";
}
}递归写法虽然看起来要简洁的多，但是若结点超级长则会导致函数调用栈溢出，所以在实现是最好使用显示调用栈的方式来实现
题目2：
题目：在O（1）的时间删除链表结点
分析：要删除一个节点，O（n）的方法是从头到尾遍历找到要删除的结点（即顺序查找），并在链表中删除它。
程序1.0 删除一个节点复杂度O（n）
void DeleteNode(ListNode**pListHead, ListNode* pToBeDeleted)
{
if (pListHead || pToBeDeleted)
return;
ListNode*cur = *pListHead;
while (cur->m_pNext != pToBeDeleted)
{
cur = cur->m_pNext;
}
cur->m_pNext = pToBeDeleted->m_pNext;
delete pToBeDeleted;
}程序2.0
删除一个结点复杂度O（1），找到要删除的结点pToBeDelete的后面的结点del，把这个结点的值覆盖要删除的结点，删除这个后面的结点
void DeleteNode(ListNode**pListHead, ListNode* pToBeDeleted)
{
if (pListHead || pToBeDeleted)//若为空
return;
if ((*pListHead == pToBeDeleted) && (pToBeDeleted->m_pNext == NULL))//只有一个节点且删除这个结点
{
delete pToBeDeleted;
pToBeDeleted = NULL;
*pListHead = NULL;
return;
}
if (pToBeDeleted->m_pNext == NULL)//有多个结点pToBeDeleted为尾节点O(N)
{
ListNode*cur = *pListHead;
while (cur->m_pNext != pToBeDeleted)
{
cur = cur->m_pNext;
}
cur->m_pNext = NULL;
delete pToBeDeleted;
pToBeDeleted = NULL;
}
else if (pToBeDeleted->m_pNext)//有多个结点且pToDeleted不为尾
{
ListNode*del = pToBeDeleted->m_pNext;
pToBeDeleted->m_value = del->m_value;
pToBeDeleted->m_pNext = del->m_pNext;
delete del;
del = NULL;
}
}题目3：
输入一个链表，输出链表中倒数第K个节点
分析：定义两个指针均指向头，一个指针先走K步，另一个等第一个指针走k步后再和其一起走，知道第一个走到空时第二个指针即走到倒数第k个节点
考虑：1.输入的头结点是否为空，访问空指针指向的内存导致程序奔溃 2.链表的结点是否大于k 3.k若为0怎么办
ListNode* FindKthToTail(ListNode*pHead, int k)
{
if (pHead == NULL || k == 0)
return NULL;
ListNode *fast = pHead;
ListNode*slow = pHead;
while (--k)
{
if (fast->m_pNext != NULL)
fast = fast->m_pNext;
else
return NULL;
}
while (fast->m_pNext)
{
slow = slow->m_pNext;
fast = fast->m_pNext;
}
return slow;
}相似快慢指针问题
1.题目：求链表中间结点
设置指向头的快、慢指针，快指针每次走两步，慢的每次走一步，当快指针走到末尾时，慢指针刚好在中间
ListNode*FindMidNode(ListNode*pHead)
{
if (pHead == NULL)
return NULL;
ListNode*fast = pHead;
ListNode*slow = pHead;
while (fast->m_pNext&&fast)
{
fast = fast->m_pNext->m_pNext;
slow = slow->m_pNext;
}
return slow;
}2.判断一个指针是否构成环形
同上方法，如果带环，则快指针一定会追上慢指针，若快指针走到了链尾（NULL），则不是环形链表
ListNode*IsCircleList(ListNode*pHead)
{
if (pHead == NULL)
return NULL;
ListNode*fast = pHead;
ListNode*slow = pHead;
while (fast&&fast->m_pNext)
{
fast = fast->m_pNext->m_pNext;
slow = slow->m_pNext;
if (slow == fast)
return slow;
}
return NULL;
}题目4：
反转链表
void ReverseList(ListNode*pHead)
{
if (pHead == NULL||pHead->m_pNext==NULL)
return;
ListNode*newHead = NULL;
ListNode*cur = pHead;
ListNode*prev = pHead;
while (cur)
{
prev = cur;
cur = cur->m_pNext;
prev->m_pNext = newHead;
newHead = prev;
}
pHead = newHead;
}题目5：
合并两个排序的链表
ListNode*Merge(ListNode*pHead1, ListNode*phead2)
{
if (pHead1 == NULL)
return phead2;
if (phead2 == NULL)
return pHead1;
ListNode*newHead = NULL;
while (pHead1&&phead2)
{
if (pHead1->m_value < phead2->m_value)
{
newHead = pHead1;
newHead->m_pNext = Merge(pHead1->m_pNext, phead2);
}
else
{
newHead = phead2;
newHead->m_pNext = Merge(pHead1, phead2->m_pNext);
}
}
return newHead;
}创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
