链表问题总结 – 源码巴士

链表相关问题在面试中出现的频率非常高。以下是我在前段时间学习《剑指offer》过程中对链表问题的总结。

单链表的创建和遍历
求单链表中节点的个数
查找单链表中的倒数第k个结点
查找单链表中的中间结点
反转链表
从尾到头打印单链表
删除链表结点

1. 单链表的创建和遍历

/** 
* 构造长度为len的单链表 
* @param len  链表中的元素个数 
* @return head  返回单链表的头指针 
*/ 
void createLinklist(LNode* &pHead,int len)  
{  
    if (len>0)
    {
        int i,data;
        scanf("%d",&data);
        pHead =(LNode*)malloc(sizeof(LNode));   //不带头结点建单链表
        if(pHead == NULL)           
            exit(EXIT_FAILURE);
        pHead->data = data;
        pHead->pNext = NULL;

        LNode* pCur = pHead;
        for(i=0;i<len-1;i++)
        {
            scanf("%d",&data);
            LNode*  pNew =(LNode* )malloc(sizeof(LNode));
            if(pNew == NULL)
                exit(EXIT_FAILURE);
            pNew->data = data;
            pNew->pNext = NULL;
            pCur->pNext = pNew;
            pCur = pCur->pNext;
        }
    }
}

/** 
* 打印单链表 
* @param head  被打印链表的头指针 
* @return void 
*/ 
void printLinklist(LNode * pNewHead)  
{  
    if(pNewHead == NULL)
        printf("NULL\n");
    else
    {  
        LNode* pCur = pNewHead;  
        while(pCur != NULL)  
        {  
            //这里主要时要注意输出的格式  
            if(pCur->pNext == NULL)  
                printf("%d\n",pCur->data);  
            else 
                printf("%d ",pCur->data);  
            pCur = pCur->pNext;  
        }  
    } 
}

2. 求单链表中节点的个数

3. 查找单链表中的倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

给定一个单向链表，找出倒数第k个节点并输出节点值。可以先让一个指针p1从链表头开始跑k歩，然后指针p2指向链表头，两指针同步向前走，当p1走到NULL时，p2即指向倒数第k点。
鲁棒检查：检查指针是否指向NULL，确保不发生内存错误。

/*
找到单链表中倒数第k个元素
*/
LNode* FindKthToLast(LNode* pHead,unsigned int k)
{ 
    if(pHead==NULL || k==0)
        return NULL;
    LNode* Head = pHead;
    LNode* Behind = pHead;
    for (unsigned int i=0;i<k-1;++i)
    {
        if (Head->pNext!=NULL)
        {
            Head=Head->pNext;
        } 
        else
        {
            return NULL;
        }
    }
    while (Head->pNext!=NULL)
    {
        Head=Head->pNext;
        Behind=Behind->pNext;
    }
    return Behind;
}

4. 查找单链表中的中间结点

普通方法：（遍历链表2次）首先计算出链表的长度size，然后输出第(size/2)个节点就可以了。

改进方法：（遍历链表1次）first和second，同时从链表头节点开始，一个指针每次移动两步，另一个每次移动一步，当走的快的指针走到链表的末尾时，走的慢的指针正好在链表的中间。

5. 合并两个有序的单链表，合并之后的链表依然有序

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

平时我经常见到合并链表的题目，考察大家的分析问题能力，编程基本功和鲁棒性。
我们需要注意的地方：

检查指针是否指向NULL。确保不发生内存错误。
合并链表要把原链表的节点拼成一条，而不是构造出一个新的链表。
如果这两个没有注意到，估计会被面试官鄙视。
时间复杂度O(m + n)
空间复杂度O(1)

/* 
合并两个升序链表，合并后的链表依然升序排列 
*/ 
LNode* Merge(LNode* pHead1,LNode* pHead2)  
{  
    if(pHead1 == NULL)  
        return pHead2;  
    if(pHead2 == NULL)  
        return pHead1;  

    LNode* pMergeHead = NULL;  
    if(pHead1->data < pHead2->data)  
    {  
        pMergeHead = pHead1;  
        pMergeHead->pNext = Merge(pHead1->pNext,pHead2);  
    }  
    else 
    {  
        pMergeHead = pHead2;  
        pMergeHead->pNext = Merge(pHead1,pHead2->pNext);  
    }  
    return pMergeHead;  
}

6. 反转链表

    输入一个链表，反转链表后，输出链表的所有元素。

反转链表是经典的链表题。反转单链表需要将链表中的每一个结点的next指针指向该结点所对应的前一个结点。这就会出现两个问题：
(1) 因为单链表中的结点只有一个指向下一个结点的next指针，没有指向前一个结点的指针，所以需要用一个指针pPre “记录”该结点的前一个结点；
(2)当我们把链表结点的next指针改为指向该结点的前一个结点后，该结点与下一个结点的链接就断开了，所以还需要用一个指针pNext“记住”下一个结点的位置。
所以需要设置三个指针，分别指向当前要反转的节点、当前要反转节点的前一个节点、当前要反转节点的下一个节点。
需要注意的是对于空链表和长度为1的链表，直接返回，不需要进行反转操作。
时间复杂度O(n)
空间复杂度O(1)

/*
反转链表，返回翻转后的头结点
*/
LNode* ReverseList(LNode* pHead)
{
    if(pHead == NULL)
        return NULL;
    if(pHead->pNext == NULL)
        return pHead;
    LNode* pCur = pHead;    //当前节点指针
    LNode* pPre = NULL;     //当前节点的前一个节点指针
    while(pCur != NULL)
    {
        LNode* pNext = pCur->pNext;//当前节点的后一个节点指针
        pCur->pNext = pPre;          //反转当前节点的指针指向前一个节点
        pPre = pCur;                //指针右移
        pCur = pNext;               //指针右移  
    }
    return pPre;            //也即反转后的头指针
}

反转链表设置三个指针，分别指向当前要反转的节点、当前要反转节点的前一个节点、当前要反转节点的下一个节点。
功能测试提前想好测试用例。

7. 从尾到头打印单链表

输入一个链表，从尾到头打印链表每个节点的值。

方法一：借用栈倒序输出链表
链表在访问时总是从头开始访问，边访问边入栈，栈的特点就是先进后出，所以出栈时就是链表的反向输入。
方法二：递归实现，完美
每访问到一个结点，就递归访问输出后面的一个结点，然后再输出结点自身，最终就是反向输出。

/*
递归从尾到头打印单链表
*/
void PrintListReverse(pNode pHead)
{
    if(pHead == NULL)
        return;
    if(pHead->next != NULL)
        PrintListReverse(pHead->next);
    printf("%d\n",pHead->data);
}

8. 删除链表结点

9. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

二叉搜索树左子树中的结点均小于根结点，右子树中的结点均大于根结点。二叉搜索树的中序遍历序列是有序的。
中序遍历递归实现，每次递归都保存一个指向已构造好的双向链表的尾节点的指针，将双向链表的最后一个节点与根节点连接在一起。

/*
采用中序遍历的方式将二叉树转化为双向链表，
*pLas指向双向链表的最后一个节点
*/
void ConvertNode(BSTree pRoot,BSTree *pLast)
{
    if(pRoot == NULL)
        return;

    //先转化左子树
    if(pRoot->left != NULL)
        ConvertNode(pRoot->left,pLast);

    //将双向链表的最后一个节点与根节点连接在一起
    pRoot->left = *pLast;
    if(*pLast != NULL)
        (*pLast)->right = pRoot;
    *pLast = pRoot;

    //转换右子树
    if(pRoot->right != NULL)
        ConvertNode(pRoot->right,pLast);
}

总结：
1. 当我们用一个指针遍历链表不能解决问题的时候，可以尝试用两个指针来遍历链表，可以让其中一个指针遍历的速度快一些（比如一次在链表中走两步），或者让它先在链表上走几步。

原文链接：https://blog.csdn.net/zhoubin1992/article/details/48975851