1 链表
创建 / 插入 / 删除 约 20行代码
有效头结点 list 要点:
(1) 插/删 可能改变 头指针 pHead -> 入参为 头指针的指针 Node** ppHead: 空 list 插入 \ 要删结点为头结点
(2) 遍历 & find: 遍历 node 为 nextNode = curNode 的 next 域 => preNodePtr 即为 curNodePtr, 不必再用1个变量记录
(3) -> 比 * 优先级高: (*ppHead)->next
// List.h
struct Node
{
int value;
struct Node* next;
};
typedef struct Node Node;
Node* CreateListNode(int value);
void ConnectListNodes(Node* pCur, Node* pNext);
void DestroyList(Node* pHead);
void AddToTail(Node** ppHead, int value);
void RemoveNode(Node** ppHead, int value);
void PrintListNode(Node* pNode);
void PrintList(Node* pHead);
// List.cpp
#include "List.h"
#include <stdio.h>
#include <stdlib.h>
Node* CreateListNode(int value)
{
Node* pNode = new Node();
pNode->value = value;
pNode->next = NULL;
return pNode;
}
void ConnectListNodes(Node* pcur, Node* pNext)
{
if(pcur == NULL)
{
printf("Error to connect two nodes.\n");
exit(1);
}
pcur->next = pNext;
}
void DestroyList(Node* phead)
{
Node* pNode = phead;
while(pNode != NULL)
{
phead = phead->next;
delete pNode;
pNode = phead;
}
}
void AddToTail(Node** ppHead, int value)
{
Node* pNew = new Node();
pNew->value = value;
pNew->next = NULL;
if(*ppHead == NULL) // 空 list 插入
*ppHead = pNew;
else
{
Node* p = *ppHead;
while(p->next != NULL)
p = p->next;
p->next = pNew;
}
}
void RemoveNode(Node** ppHead, int value)
{
if(ppHead == NULL || *ppHead == NULL)
return;
Node* pToBeDeleted = NULL;
if((*ppHead)->value == value ) // 要删结点为头结点
{
pToBeDeleted = *ppHead;
*ppHead = (*ppHead)->next;
}
else
{
Node* p = *ppHead;
// 遍历 & find: 遍历 node 为 nextNode = curNode 的 next 域 => preNodePtr 即为 curNodePtr
while(p->next != NULL && p->next->value != value)
p = p->next;
// found
if(p->next != NULL && p->next->value == value)
{
pToBeDeleted = p->next;
p->next = p->next->next;
}
}
if(pToBeDeleted != NULL)
{
delete pToBeDeleted;
pToBeDeleted = NULL;
}
}
void PrintListNode(Node* pNode)
{
if(pNode == NULL)
printf("The node is NULL\n");
else
printf("The key in node is %d.\n", pNode->value);
}
void PrintList(Node* phead)
{
printf("PrintList starts.\n");
Node* pNode = phead;
while(pNode != NULL)
{
printf("%d\t", pNode->value);
pNode = pNode->next;
}
printf("\n PrintList ends.\n");
}
Que5 从尾到头
打印链表
input: pHead
solu1: stack
std::stack<Node*> pNodesStack
遍历 & 入栈 -> top - print - pop
solu2: 递归: 本质也是栈
每访问 1 个 Node, 先 递归访问 其后 Nodes
Prob: 链表太长时, 栈函数调用栈溢出
// PrintListReversly.cpp
#include "..\Utilities\List.h"
#include <stack>
void PrintListReversIter(Node* pHead)
{
std::stack<Node*> pNodesStack;
Node* pnode = pHead;
while(pnode != NULL)
{
pNodesStack.push(pnode);
pnode = pnode->next;
}
while(!pNodesStack.empty() )
{
pnode = pNodesStack.top();
printf("%d\t", pnode->value);
pNodesStack.pop();
}
}
// 每访问 1 个 Node, 先 递归访问其后 Nodes
void PrintListReversRecurs(Node* pHead)
{
if(pHead != NULL)
{
if (pHead->next != NULL)
PrintListReversRecurs(pHead->next);
printf("%d\t", pHead->value);
}
}
void Test(Node* pHead)
{
PrintList(pHead);
PrintListReversIter(pHead);
printf("\n");
PrintListReversRecurs(pHead);
}
// 1->2->3
void Test1()
{
printf("\nTest1 begins.\n");
Node* pNode1 = CreateListNode(1);
Node* pNode2 = CreateListNode(2);
Node* pNode3 = CreateListNode(3);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
Test(pNode1);
DestroyList(pNode1);
}
// 只有一个结点的链表: 1
void Test2()
{
printf("\nTest2 begins.\n");
Node* pNode1 = CreateListNode(1);
Test(pNode1);
DestroyList(pNode1);
}
// 空链表
void Test3()
{
printf("\nTest3 begins.\n");
Test(NULL);
}
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
}
Que13 O(1) 时间删 指定 node
input: 头结点(pHead 或 ppHead), pToBeDeleted
普通 delete: O(n)
[1] 遍历 + find pToBeDeletedPre
[2] 换链: pToBeDeletedPre->next = pToBeDeleted->next
[3] delete pToBeDeleted
[4] pToBeDeleted = NULL; // safe, 可有可无
O(1) 删: 基于假设 pToBeDeleted 在 list 中, 把 判 pToBeDeleted 是否在 list 中 ( O(n) ) 的责任 推给 caller
(1) case1: pToBeDeleted 不是尾(结点)
pToBeDeleted pnext = pToBeDeleted->next
_ _ _ _ _ _ _ _
| _ | _ _ _\ | _ | _ _\
|_ _ _ _| / |_ _ _ _| /
[1] value copy: pToBeDeleted->value = pnext->value;
[2] 换链 : pToBeDeleted->next = pnext->next; // pToBeDeleted->next->next
[3] delete : pnext
条件: 用 pToBeDeleted->next->next => 要求 pToBeDeleted->next != NULL, 即 pToBeDeleted 不是尾(结点)
(2) case2: pToBeDeleted 是尾 不是头(list 不只1个 node)
pprev pToBeDeleted
_ _ _ _ _ _ _ _
| _ | _ _ _\ | _ | _ _\ NULL
|_ _ _ _| / |_ _ _ _| /
[1] pprev->next = NULL;
[2] delete pToBeDeleted;
Note: 要先找 pprev -> O(n), 但 case2 只占 1/n => 平均 T(n) = [(n-1)*O(1) + O(n)] / n = O(1)
条件: [1] 用 pprev->next => 要求 pprev != NULL <=> pToBeDeleted 不是头结点: pToBeDeleted != *ppHead
即 pToBeDeleted 是尾 不是头(list 不只1个 node)
(3) case3: pToBeDeleted 是尾也是头 (list 只有1个结点)
=> pHead 被改 => 入参 ppHead
*ppHead == pToBeDeleted
_ _ _ _
| _ | _ _\ NULL
|_ _ _ _| /
[1] delete pToBeDeleted;
[2] *ppHead = NULL;
// DeleteNodeO1InList.cpp
#include "..\Utilities\List.h"
#include <stdio.h>
void DeleteNode(Node** ppHead, Node* pToBeDeleted)
{
if(!ppHead || !pToBeDeleted)
return;
// case1: pToBeDeleted 不是尾(结点)
if(pToBeDeleted->next != NULL) // else if / else 分支: pToBeDeleted 是尾
{
Node* pnext = pToBeDeleted->next;
pToBeDeleted->value = pnext->value;
pToBeDeleted->next = pnext->next;
delete pnext;
// pnext = NULL; // safe
}
else if(*ppHead == pToBeDeleted) // case3: pToBeDeleted 是尾也是头 (list 只有1个结点)
{
*ppHead = NULL;
delete pToBeDeleted;
// pToBeDeleted = NULL; // safe
}
else // case2: pToBeDeleted 是尾 不是头(list 不只1个 node)
{
Node* pprev = *ppHead;
// find pprev
while(pprev->next != pToBeDeleted)
pprev = pprev->next;
pprev->next = NULL;
delete pToBeDeleted;
// pToBeDeleted = NULL; // safe
}
}
void Test(Node* ppHead, Node* pnode)
{
printf("The original list is: \n");
PrintList(ppHead);
printf("The node to be deleted is: \n");
PrintListNode(pnode);
DeleteNode(&ppHead, pnode);
printf("The result list is: \n");
PrintList(ppHead);
}
// 链表中有多结点, 删中间结点
void Test1()
{
Node* pNode1 = CreateListNode(1);
Node* pNode2 = CreateListNode(2);
Node* pNode3 = CreateListNode(3);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
Test(pNode1, pNode3);
DestroyList(pNode1);
}
// 空链表
void Test5()
{
Test(NULL, NULL);
}
int main(int argc, char* argv[])
{
Test1();
Test5();
return 0;
}
Que15 单链表 倒数第 k 个节点
input: phead
output: 倒数第 k 个节点(尾: 倒数第1个节点)
solu1: list 有 n 个 node => 倒数 第 k 个 == 正数 第 n - k + 1 个
[1] 先求 nodes 数 n : 遍历 list
[2] 再从头往后走 n - k + 1 步: 遍历 list
=> 2 次遍历
solu2: 双指针
[1] p1/p2 都从 pHead 开始, p1 先走 k-1 步 => p1/p2 相距 k - 1 步
[2] 两者联动, p1/p2 走到 尾/倒数第k个node
Node:
(1)若 n < k <=> p1 走不到 第 k-1 步 就已经到 list 尾了
(2) 整型 有减时, 要考虑减为负。unsigned 若看似减为负, 实际变成大正数
// KthNodeFromEnd.cpp
#include "..\Utilities\List.h"
#include <stdio.h>
Node* FindKthToTail(Node* pHead, unsigned int k)
{
if(pHead == NULL || k == 0)
return NULL;
Node *p1 = pHead;
Node *p2 = pHead;
// (1) p1 先走 k-1 步,
for(unsigned int i = 0; i < k - 1; ++ i) // k - 1: unsigned
{
if(p1->next != NULL)
p1 = p1->next;
else // 若 走不到 第 k - 1 步 就已经到 list 尾了, nodes 数 < k => return NULL
return NULL;
}
// (2) p1 & p2 开始联动
while(p1->next != NULL)
{
p1 = p1->next;
p2 = p2->next;
}
return p2;
}
// 测试要找的结点在链表中间
void Test1()
{
printf("=====Test1 starts:=====\n");
Node* pNode1 = CreateListNode(1);
Node* pNode2 = CreateListNode(2);
Node* pNode3 = CreateListNode(3);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
printf("expected result: 1.\n");
Node* pNode = FindKthToTail(pNode1, 3);
PrintListNode(pNode);
DestroyList(pNode1);
}
// 空链表
void Test2()
{
printf("=====Test4 starts:=====\n");
printf("expected result: NULL.\n");
Node* pNode = FindKthToTail(NULL, 100);
PrintListNode(pNode);
}
int main(int argc, char* argv[])
{
Test1();
Test2();
}
延伸:
15.1 求 list 中间节点, list nodes 数为 奇/偶 -> return mid / 2个 mid 中任一个
双指针: p1/p2 1次 walk 2/1 步 => p1/p2 到 尾/中间
15.2 判 单 list 是否有环
双指针: p1/p2 1次 walk 2/1 步 -> 若 p1 追上 p2, 则有环
找 环起始点: Floyd 判圈法
第1次相遇, p1 移到 pHead, p1/p2 后面每次 walk 1 步, 第2次相遇点为 环起始点
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
| _ | _ _ _\ | _ | _ _\ | _ | _ _ _\ | |
|_ _ _ _| / |_ _ _ _| / |_ _ _ _| / |_ _ _ _|
|\ |
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
Node* detectCycle(Node* pHead)
{
Node* p1 = pHead;
Node* p2 = pHead;
// judge whether there's cycle
do
{
if(!p1 || !p1->next)
return NULL;
p1 = p1->next->next;
p2 = p2->next;
} while(p1 != p2)
// find cycle start
p1 = pHead;
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
}
Que16 反转 单链表
input: 头指针 pHead
output: 反转后的头指针 pReversHead
画图: 图中 node 也可以为 NULL
(1) 通用图
(2) 使用 p->next => 前提条件 p != NULL
(3) 要 record/store 的 ptr: pnext / pprev, 以使指向 target 的链断开后, 仍能找到 target
(4) 要计算的 ptr
(5) ptr 合理初值
(6) 边界
pnode / pnext / pprev == NULL
(1) 通用图
当前节点 pnode 前面节点已处理完 => 已反转
pprev pnode
_ _ _ _ _ _ _ _ _ _ _ _
... | | | _ | _ _\ | _| _ _\
|\ |_ _ _| _| |_ _ _ _| / |_ _ _ _| /
|_ _ _ _ _|
process pnode
pprev pnode pnext
_ _ _ _ _ _ _ _ _ _ _ _
... | | | | | _ | _ _\
|\ |_ _ _| _| |_ _ _|_| |_ _ _ _| /
| | |\ |
|_ _ _ _ _| |_ _ _ _ _ _ _|
[1] store pnext: pnext = pnode->next;
[2] 变链: pnode->next = pprev
[3] pprev & pnode 后移
pprev = pnode;
pnode = pnext;
pprev pnode
_ _ _ _ _ _ _ _ _ _ _ _
... | | | | | _ | _ _\
|\ |_ _ _| _| |_ _ _|_| |_ _ _ _| /
| | |\ |
|_ _ _ _ _| |_ _ _ _ _ _ _|
pnext = pnode->next;
pnode->next = pprev
pprev = pnode;
pnode = pnext;
(2) 用 pnode->next => 前提: pnode != NULL
while(pnode != NULL)
{
pnext = pnode->next;
pnode->next = pprev
pprev = pnode;
pnode = pnext;
}
(3) 要 store 的 ptr: pnext, 以使指向 target/pnext 的链断开后, 仍能找到 target/pnext
pnext = pnode->next;
(4) pReverseHead: return 与 赋值
pReverseHead 何时赋值? 处理 the last node 时 <=> pnext == NULL
while(pnode != NULL)
{
pnext = pnode->next;
if(pnext == NULL)
pReverseHead = pnode;
pnode->next = pprev
pprev = pnode;
pnode = pnext;
}
return pReverseHead;
(5) ptr 合理初值
pReverseHead = NULL;
pprev = NULL;
pnode = pHead;
while(pnode != NULL)
{
pnext = pnode->next;
if(pnext == NULL)
pReverseHead = pnode;
pnode->next = pprev
pprev = pnode;
pnode = pnext;
}
return pReverseHead;
(6) 边界: 带入看是否OK
pprev == NULL; OK
pnode == NULL; 处理第1个 node, OK
pnext == NULL; 处理最后1个 node, OK
=>
Node* ReverseList(Node* pHead)
{
Node* pReverseHead = NULL;
Node* pprev = NULL;
Node* pnode = pHead;
while (pnode != NULL)
{
Node* pnext = pnode->next;
if (pnext == NULL)
pReverseHead = pnode;
pnode->next = pprev;
pprev = pnode;
pnode = pnext;
}
return pReverseHead;
}
// ReverseList.cpp
#include "..\Utilities\List.h"
#include <stdio.h>
Node* ReverseList(Node* pHead)
{
Node* pReverseHead = NULL;
Node* pprev = NULL;
Node* pnode = pHead;
while (pnode != NULL)
{
Node* pnext = pnode->next;
if (pnext == NULL)
pReverseHead = pnode;
pnode->next = pprev;
pprev = pnode;
pnode = pnext;
}
return pReverseHead;
}
Node* Test(Node* phead)
{
printf("The original list is: \n");
PrintList(phead);
Node* pReverseHead = ReverseList(phead);
printf("The reversed list is: \n");
PrintList(pReverseHead);
return pReverseHead;
}
// 输入的链表有多个结点
void Test1()
{
Node* pNode1 = CreateListNode(1);
Node* pNode2 = CreateListNode(2);
Node* pNode3 = CreateListNode(3);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
Node* pReverseHead = Test(pNode1);
DestroyList(pReverseHead);
}
void Test2()
{
Node* pNode1 = CreateListNode(1);
Node* pReverseHead = Test(pNode1);
DestroyList(pReverseHead);
}
// 空链表
void Test3()
{
Test(NULL);
}
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
}
Que17 合并2个已排序(递增) list
分析: 1次合并之后的状态
小头结点合并到新链表后, 2 个 list 剩余 nodes 仍是已排序的 => 合并步骤 与之前步骤一样
=> 递归
过程
_ _ _ _ _ _ _ _ _ _ _ _
| 1 _| _ _ _\ | 3 _ | _ _\ | 5 |
|_ _ _ _| / |_ _ _ _| / |_ _ _ _|
_ _ _ _ _ _ _ _ _ _ _ _
| 2 _| _ _ _\ | 4 _ | _ _\ | 6 |
|_ _ _ _| / |_ _ _ _| / |_ _ _ _|
phead1
_ _ _ _ _ _ _ _
| 3 _| _ _\ | 5 |
|_ _ _ _| / |_ _ _ _|
phead
_ _ _ _ ?
| 1 _| _ _\
|_ _ _ _| phead2
_ _ _ _ _ _ _ _ _ _ _ _
| 2 _| _ _ _\ | 4 _ | _ _\ | 6 |
|_ _ _ _| / |_ _ _ _| / |_ _ _ _|
第1次合并后的 phead->next 等 下一层递归时 才知道: 是下一层递归的 phead => 递归
// MergeSortedLists.cpp
#include "..\Utilities\List.h"
#include <stdio.h>
Node* Merge(Node* phead1, Node* phead2)
{
// (1) 递归出口
if(phead1 == NULL)
return phead2;
else if(phead2 == NULL)
return phead1;
// (2) 每次递归 phead 初始化为 NULL
Node* phead = NULL;
if(phead1->value < phead2->value)
{
phead = phead1; // (3) phead 计算 & 入栈
// (4) phead->next 等 下一层递归时 才知道: 是下一层递归的 phead => 递归
phead->next = Merge(phead1->next, phead2);
}
else
{
phead = phead2;
phead->next = Merge(phead1, phead2->next);
}
return phead; // (5) phead 出栈
}
Node* Test(const char* testName, Node* phead1, Node* phead2)
{
if(testName != NULL)
printf("%s begins:\n", testName);
printf("The first list is:\n");
PrintList(phead1);
printf("The second list is:\n");
PrintList(phead2);
printf("The merged list is:\n");
Node* phead = Merge(phead1, phead2);
PrintList(phead);
printf("\n\n");
return phead;
}
// list1: 1->3->5
// list2: 2->4->6
void Test1()
{
Node* pNode1 = CreateListNode(1);
Node* pNode3 = CreateListNode(3);
Node* pNode5 = CreateListNode(5);
ConnectListNodes(pNode1, pNode3);
ConnectListNodes(pNode3, pNode5);
Node* pNode2 = CreateListNode(2);
Node* pNode4 = CreateListNode(4);
Node* pNode6 = CreateListNode(6);
ConnectListNodes(pNode2, pNode4);
ConnectListNodes(pNode4, pNode6);
Node* phead = Test("Test1", pNode1, pNode2);
DestroyList(phead);
}
// 一个链表为空: list1: 1->3->5 / list2: 空
void Test2()
{
Node* pNode1 = CreateListNode(1);
Node* pNode3 = CreateListNode(3);
Node* pNode5 = CreateListNode(5);
ConnectListNodes(pNode1, pNode3);
ConnectListNodes(pNode3, pNode5);
Node* phead = Test("Test2", pNode1, NULL);
DestroyList(phead);
}
// 两个链表均空
void Test3()
{
Node* phead = Test("Test3", NULL, NULL);
}
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
}
Que37 2 个单链表 第1个 公共结点
solu1: 分析 有公共 node 的 2 个 list 的特点
从 第1个公共 node(在 list 尾部) 开始, 之后所有 node 重合
_ _ _ _ _ _ _ _ _ _ _ _
| 1 _| _ _ _\ | 2 _ | _ _\ | 3 |
|_ _ _ _| / |_ _ _ _| / |_ _ _ _| \ _ _ _ _ _ _ _ _
\ _ | 6 | _ _\ | 7 |
/ |_ _ _ _| / |_ _ _ _|
/
_ _ _ _ _ _ _ _
| 4 _ | _ _\ | 5 |
|_ _ _ _| / |_ _ _ _|
从 尾部倒着比较: 最后到达尾结点, 却要先被比较 -> 后进先出: Stack
list1: stack1
list2: stack2
尾部均在栈顶
record stack1 栈顶 = NULL
cmp 栈顶
[1] ==
record stack1 栈顶
continue cmp 栈顶
[2] !=
break
上次记录的 stack1 栈顶 即 target
需 2个辅助 stack => 空间复杂度 O(n1 + n2)
时间复杂度 O(n1 + n2)
solu2: 双指针
第1次遍历: 2 个 list 长度 => 长度差 D
第2次遍历: 长 list 上先走 D 步(=> 剩余部分 2 个 list 一样长), 再 在 2个 list 上 同时走, 第1个相同 node 为 target
T(n1, n2) = O(n1 + n2)
空间复杂度: 无需 辅助 stack
延伸 图逆转 90度: 2 个 list 第1个公共 node 正是 二叉树 2 个 leaf node 的 最低公共祖先
#include "..\Utilities\List.h"
#include <stdio.h>
unsigned int GetListLength(Node* pHead);
Node* FindFirstCommonNode( Node *pHead1, Node *pHead2)
{
// (1) 求 2 list 长度
unsigned int len1 = GetListLength(pHead1);
unsigned int len2 = GetListLength(pHead2);
int distance = 0;
Node* pLong = NULL;
Node* pShort = NULL;
if (len1 > len2)
{
distance = len1 - len2;
pLong = pHead1;
pShort = pHead2;
}
else
{
distance = len2 - len1;
pLong = pHead2;
pShort = pHead1;
}
// (2) 长 list 上先走 D 步 => 剩余部分 2 个 list 一样长
for(int i = 0; i < distance; ++ i)
pLong = pLong->next;
// (3) 在 2个 list 上 同时走, 第1个相同 node 为 target
while( pLong != NULL && pShort != NULL && pLong != pShort)
{
pLong = pLong->next;
pShort = pShort->next;
}
// (3) 必为 pLong == pShort == NULL (无公共 node) 或 pLong == pShort != NULL ( 得到第一个公共结点 )
Node* pFisrtCommonNode = pLong;
return pFisrtCommonNode;
}
unsigned int GetListLength(Node* pHead)
{
unsigned int len = 0;
Node* p = pHead;
while(p != NULL)
{
++len;
p = p->next;
}
return len;
}
void Test(const char* testName, Node* pHead1, Node* pHead2, Node* pExpected)
{
if(testName != NULL)
printf("%s begins: ", testName);
Node* pResult = FindFirstCommonNode(pHead1, pHead2);
if(pResult == pExpected)
printf("Passed.\n");
else
printf("Failed.\n");
}
// 第一个公共结点在链表中间
// 1 - 2 \
// 4 - 5
// 3 /
void DestroyNode(Node* pNode)
{
delete pNode;
pNode = NULL;
}
void Test1()
{
Node* pNode1 = CreateListNode(1);
Node* pNode2 = CreateListNode(2);
Node* pNode3 = CreateListNode(3);
Node* pNode4 = CreateListNode(4);
Node* pNode5 = CreateListNode(5);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode4);
ConnectListNodes(pNode3, pNode4);
ConnectListNodes(pNode4, pNode5);
Test("Test1", pNode1, pNode4, pNode4);
DestroyNode(pNode1);
DestroyNode(pNode2);
DestroyNode(pNode3);
DestroyNode(pNode4);
DestroyNode(pNode5);
}
// 没有公共结点
// 1 - 2
// 5
void Test2()
{
Node* pNode1 = CreateListNode(1);
Node* pNode2 = CreateListNode(2);
Node* pNode5 = CreateListNode(5);
ConnectListNodes(pNode1, pNode2);
Test("Test2", pNode1, pNode5, NULL);
DestroyList(pNode1);
DestroyList(pNode5);
}
// 有一个空链表
void Test3()
{
Node* pNode1 = CreateListNode(1);
Node* pNode2 = CreateListNode(2);
Node* pNode3 = CreateListNode(3);
ConnectListNodes(pNode1, pNode2);
ConnectListNodes(pNode2, pNode3);
Test("Test3", NULL, pNode1, NULL);
DestroyList(pNode1);
}
// 2个空 list
void Test4()
{
Test("Test4", NULL, NULL, NULL);
}
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
}
45 圆圈中最后剩下的数字: 约瑟夫环
n 个数字 0, 1, ..., n-1 围成1圈, 从 0 开始每次删第 m 个数, 求最后剩下的数
m = 3
1 2 3 4
0, 1, 2, 3, 4 -> 0, 1, 3, 4 -> 1, 3, 4 -> 1, 3 -> 3
用 环形链表: STL std::list
/ 自己实现环形链表(单链表即可)
std::list 迭代器 ++ 若遇 无效尾结点 end(), 则 跳到 begin(); -- 不用
// LastNumberInCircle.cpp
#include <list>
// === method1
int LastRemaining(unsigned int n, unsigned int m)
{
if(n < 1 || m < 1)
return -1;
unsigned int i = 0;
std::list<int> numsList;
for(i = 0; i < n; ++ i)
numsList.push_back(i);
std::list<int>::iterator curIter = numsList.begin();
while(numsList.size() > 1)
{
// (1) 走 m - 1 步
for(unsigned int i = 0; i < m-1; ++ i)
{
curIter ++;
if(curIter == numsList.end() )
curIter = numsList.begin();
}
// (2) record nextIter
std::list<int>::iterator nextIter = ++curIter;
if(nextIter == numsList.end())
nextIter = numsList.begin();
// (3) 删 curNode
-- curIter;
numsList.erase(curIter);
// (4) 下一次循环 的 起点 curIter
curIter = nextIter;
}
return *(curIter);
}
void Test(const char* testName, unsigned int n, unsigned int m, int expected)
{
if(testName != NULL)
printf("%s begins: \n", testName);
if(LastRemaining(n, m) == expected)
printf("passed.\n");
else
printf("failed.\n");
printf("\n");
}
void Test1()
{
Test("Test1", 5, 3, 3);
}
void Test2()
{
Test("Test2", 5, 2, 2);
}
void Test3()
{
Test("Test3", 0, 0, -1);
}
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
}
网友评论