美文网首页
链表: swordToOffer

链表: swordToOffer

作者: my_passion | 来源:发表于2022-07-18 11:19 被阅读0次

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();
}

相关文章

  • 链表: swordToOffer

    1 链表 有效头结点 list 要点: (1) 插/删 可能改变 头指针 pHead -> 入参为 头指针的指针 ...

  • 树: swordToOffer

    树 递归: 3 要素 (1) 递归函数: paras/returnValue (2) 终止条件 (3) 本层递归逻...

  • 数组: swordToOffer

    数组 (1) 创建时要分配固定容量 => 经常有空闲区 => 空间效率低 解决: 动态数组 std::vector...

  • others: swordToOffer

    预留

  • 栈/队列: swordToOffer

    栈/队列 Que7: 用 2 个栈实现队列 Que 类: 成员数据: 2 个 std::stack2个成员函数: ...

  • 字符串: swordToOffer

    字符串 以 '\0' 结尾 (1) 常量字符串: 放 只读段 .rodata (2) 字符数组: 用 常量字符串 ...

  • 海量数据处理: swordToOffer

    海量数据处理 Que30 最小的 k 个数 O(n * logk) (1) 用1个容器( std::multise...

  • 链表基础

    链表基础 链表长度 链表为空 链表结构 链表增加

  • 双向链表&双向循环链表

    链表分为:单链表、单向循环链表、双向链表、双向循环链表本节主要说明:双向链表、双向循环链表 定义结点 一、双向链表...

  • 算法与数据结构:链表

    链表 链表还分为单向链表和双向链表, 但是这篇文章只说单向链表 , 下次再讲双向链表 . 链表和数组的区别 ? 链...

网友评论

      本文标题:链表: swordToOffer

      本文链接:https://www.haomeiwen.com/subject/eivqirtx.html