【数据结构】链表OJ面试题(题库+解析)

前言

还不清楚链表的码喵们可以看看前篇关于链表的详解

http://t.csdnimg.cn/X6t6P

1.链表面试题

既然已经懂得了链表该如何实现，那么现在就趁热打铁开始练习！这里给码喵们整理了相对不错的一些OJ题来练习

1. 删除链表中等于给定值 val 的所有结点。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路：遍历整个表，访问每个表的值并且删除再将next的指针指向下一个节点

此题比较简单，但是有几个要点来考虑：

如果第一位是需要删除的数
执行删除时要如何保存此值的地址来进行空间释放
等于val值执行删除
不等于val的值执行向下遍历

附原代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode *tail=head;
    struct ListNode *prev=NULL; //用于记录节点在free掉的时候避免找不到
    
    while(tail!=NULL)   //不为尾节点向后遍历
    {
        if(tail->val == val)    //如果第一位是需要删除的数
        {
            if(tail==head)
            {
                head=tail->next;
                free(tail);
                tail = head;
            }
            else                //执行删除节点，并且free掉空间避免空指针或溢出
            {
            prev->next = tail->next;
            free(tail);
            tail = prev->next;
            }
        }
        else
        {
            prev = tail;
            tail=tail->next;
        }
    }
    return head;
 }

2. 反转一个单链表。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

本题有些难度，但是掌握好方法后类似的题就能做到运筹帷幄（决胜千里之外）

万事开头难，掌握方法微妙，刚开始我做这题的时候想的是把他变成一个循环指针然后再标记头指针并且实现反转，不知道这样的办法大家有没有试过哈哈，现在我们来用更简单的方法吧。

我们来指定三个指针，前两个指针用于将前一个的指针记录并且连接，第三个指针负责向后遍历直到为空

方法1

定义三个指针

n1滞空用于将头指针变成新链表的尾指针，所以滞空

n2 ,n3向后遍历

首先我们让n2的下一个结点指向n1,实现第二和第一个节点的相连，再让n2=n3改变n2的地址，再让n3向下一个节点移动

n3再向下一个节点移动，之后循环到n2为空地址，就完成了所有节点的反转了。

注意要点：

链表初始值为空要怎么处理
链表的n2最终到哪里才算结束反转
指针n3的下一个节点若为空怎么办（不能赋值否则会越界）

附原代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode * n1,*n2,*n3;
    n1=NULL;
    n2=head;
    if(n2)
        n3=n2->next;

    while(n2)
    {
        n2->next = n1;

        n1=n2;
        n2 = n3;

        if(n3)
            n3=n3->next;
    }
    return n1;
}

方法2

我们可以采用头插到新表的方法实现反转，头插进NULL的表，每次插入的数据就是原表按顺序遍历。

定义一个新表为空

再让原表的cur的下一个节点指向newhead，这样就实现了头插，然后我们再定义一个指针来记录原cur的下一个节点，最后再将newhead指向cur,cur指向下一个节点next.

循环这个操作，直到cur为NULL

返回newhead

附原代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur=head;
    struct ListNode* newhead = NULL;

    while(cur)
    {
        struct ListNode* next=cur->next;
        cur->next = newhead;    //指向新节点
        newhead = cur;

        cur = next;
    } 
   return newhead;
}

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

这就要运用上非常巧妙的方法了，既然上一题我们用到了三个指针，这道题我们也用指针来做，但是只用两个指针就好

方法

我们定义两个指针都在头节点向后遍历，但是一个节点一次走一步，一个节点一次走两步

当tail走到最后的节点时，head节点刚好返回的就是中间值。

注意要点：

tail走两步，head走一步，返回head的地址就是中间的地址
如果tail走到尾要怎么处理

附源代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* middleNode(struct ListNode* head) {
     struct ListNode* tail = head;
     while(tail->next)
     {
         head=head->next;
         tail=tail->next;
         if(tail->next==NULL)
         {
         //head=head->next;
         }
         else
         tail=tail->next;
     }
     return head;

    // struct ListNode* tail = head;
    // int count=0;
    // while(tail->next)
    // {
    //     count++;
    //     tail = tail->next;
    // }
    // if(count%2!=0)
    // {
    //     count=(count+1)/2;
    // }
    // else
    // count/=2;
    // while(count--)
    // {
    //     head=head->next;
    // }
    // return head;
}

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

链表中倒数第k个结点_牛客题霸_牛客网

此题是上一题的升级版，方法相似，上一题是相对移动，本体是相对距离再移动

方法

这次我们定义两个指针，一个first指针先向前走k步，之后在first和tail指针一起向前走，直到first指针走到结尾，返回tail指针

注意要点

first指针走到尾该如何处理
空的链表该如何处理
k等于链表的长度该返回什么值（返回第一个节点）
k大于链表的长度该返回什么值（不是我想思考，是nt牛客的测试用例真有这几点，吃饱撑着）

附源代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
	if (pListHead == NULL)	//链表为空直接返回NULL
	{
		return pListHead;
	}
	struct ListNode* first = pListHead;
	struct ListNode* tail = pListHead;

	while (first->next)	//直到first走到尾
	{
		while (k > 0 && first->next)	//k没减到0并且first还没走到尾进入循环
		{
			k--;	//这里用k自减1来进行k次循环的实现（k=0侧不执行）
			first = first->next;
			//if (first->next == NULL && k > 0)
			//{
			//	return NULL;
			//}
		}
		if (first->next == NULL&&k==1)		//当k减到1并且first已经走到尾
		{
			return tail;				//我们就可以直接返回tail的值，这就是返回第一个节点
		}
		else if(k>1)					//如果first到达尾，并且k还大于1，那就是k大于整个链表长度的情况
		{
			return NULL;				//直接返回NULL
		}
		tail = tail->next;		//tail向下走一步
		first = first->next;	//frist向下走一步
	}
	//tail=tail->next;
	return tail->next;
}



    // int count = k;

    // while(first->next)
    // {
    //     first=first->next;
    // }
    //     int len = count;
    // while(tail->next)
    // {
    //     while(len--)
    //     {
    //         tail=tail->next;
    //     }
    //     if(tail!=first)
    //     {
    //         len = count;
    //     }
    //     else 
    //     {
    //         return pListHead->next;
    //     }

    //     pListHead = tail;
    // }
    // return 0;
    // write code here

5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

方法

照图来看，我们可以很明显的知道我们可以把新的数据放入“新的“链表，这里的引号，意思是这种合并的题目，我们可以不创建新的空间，因为链表的特性，就是每个都是一块独立的空间，而我们就可以把这些表重新”排序“使之形成一个新的链表，而这里的排序方法就是：比较较小值，尾插入新表中。

新建两个链表

当新表为空时，将较小值（list1）的地址直接赋值，并且更新list1使之向后走，这里因为list1、list2相等，所以随便取一个就行。

依此类推，list2、list1对比时，list2较小，将list2赋值list3,同时更新。

最后当其中一个表（list2）所有值都赋值给新表后，在把另一个表的所有值直接尾插到新表就OK了，不管另一个表后有多少个值，都可以直接尾插并且完成链表的合并

之后返回我们记录的tail就完成了（真是功夫不负有心人啊）

注意要点：

初始创建表时，首节点为空，我们要让它赋值原表的地址，应该分类讨论
注意各表的更新
当其中一个表中所有的值都赋值完毕，另外一个表就可以全部尾插入新表中

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    struct ListNode* list3=NULL;
    struct ListNode* tail=NULL;
    if(list1==NULL)
    {
        return list2;   //若其中一个表为空则返回另一个表
    }
    if(list2==NULL)
    {
        return list1;   //若其中一个表为空则返回另一个表
    }

    while(list1&&list2)
    {
        if(list1->val>list2->val)   //返回小的值
        {
            if(list3==NULL)
            {
                tail=list3=list2;   //如果新链表没有头则把较小值的地址赋值
            }
            else
            {
                list3->next = list2;    //新链表的下一个节点指向较小值
                list3=list3->next;      //更新新链表
            }
            list2=list2->next;          //更新已被赋值的较小值链表首地址
        }
        else if(list1->val<list2->val)
        {
            if(list3==NULL)
            {
                tail=list3=list1;   //如果新链表没有头则把较小值的地址赋值
            }
            else
            {
                list3->next = list1;
                list3=list3->next;
            }
            list1=list1->next;
        }
        else                //两值相同则赋值其中一个链表的首地址
        {
            if(list3==NULL)
            {
                tail=list3=list1;   //如果新链表没有头则把较小值的地址赋值
            }
            else
            {
                list3->next = list1;
                list3=list3->next;
            }
            list1=list1->next;
        }
    }   
    if(list1)       //其中一个表全部赋值完毕，侧再把另一个表的剩下值尾插到新表
    {
        list3->next=list1;
        return tail;
    } 
    else if(list2)
    {
        list3->next=list2;
        return tail;
    }
    else
    {
        return tail;
    }

}

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。OJ链接

7. 链表的回文结构。OJ链接

8. 输入两个链表，找出它们的第一个公共结点。OJ链接