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

1.前言

前五题在这http://t.csdnimg.cn/UeggB

休息一天，今天继续刷题！

2.OJ题目训练

1. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。链表分割_牛客题霸_牛客网

思路

既然涉及到链表分割并且原本的数据的顺序不能改变，那我们就要用到两个新的链表来存放值，一边存放小于x的，右边按顺序存放大于x的，最后再将两个链表连起来形成新的链表，就可以完成此题。

整个链表，红色底线为小于3的值，大于为绿色底线

遍历整个表将小于x的值放入ghead中，同时更新gtail的值。

再将大于等于x的值放入Lhead表中，更新Ltail的值

最后再通过gtail(前表尾节点)和Lhead(后表头节点)相连。返回ghead既为合并的表。

注意要点

涉及到改变头节点的方法，应该添加标兵节点，这样若其中一个表为空，也不会报错
比x小的值在比x大的值后面的情况，那他就会指回L表，造成回环（假设第二个1本来是在4的后面，所以4的next节点还是指向1）
释放标兵节点

附源代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cstdlib>
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode *ghead,*gtail,*Lhead,*Ltail;
        ghead = gtail = (struct ListNode *) malloc(sizeof(struct ListNode));
        Lhead = Ltail = (struct ListNode *) malloc(sizeof(struct ListNode));
        struct ListNode *cur = pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                Ltail->next = cur;
                cur = cur->next;
                Ltail=Ltail->next;
            }
            else 
            {
                gtail->next = cur;
                cur = cur->next;
                gtail=gtail->next;               
            }
        }
        Ltail->next = ghead->next;
        struct ListNode * a = Lhead->next;

        gtail->next = NULL; //防止比x大的最后一个值下一个节点指向其他的值（比x小的值在他后面的情况，那他就会指回L表，造成回环）
        free(Lhead);
        free(ghead);
        return a;
    }
};

2. 链表的回文结构。

首先科普一下回文

可以形象的理解为：正态分布就为回文，反之不是。

方法

由于回文的基本特性我们可以，将回文分成一半一半的两部分，然后进行比较

分成红底进行比较，但是由于链表的特殊性，我们不能倒着比较。

所以就要对另一半进行逆序来比较

逆序后进行比较。

这样我们就可以用到我们之前题目的积累，正所谓功夫不负有心人，CV大法启动！

附上链接：

2. 反转一个单链表。

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

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

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

注意要点

中间节点要记录好，因为后续比较要用到
该如何判断比较的继续条件（任何一个为NULL就结束）

附源代码：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:

    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* 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;
}


    bool chkPalindrome(ListNode* A) {
    struct ListNode* mid = middleNode(A);
    struct ListNode* rev = reverseList(mid);
    while(A&&rev)
    {
        if(A->val!=rev->val)
        {
            return false;
        }
        A=A->next;
        rev=rev->next;
    }
    return true;
}
};

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

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

方法

大家要注意相交的链表的意思是后面的节点会交汇，而不是交叉相交

根据这种链表的特点，我们可以清楚他们的尾节点一定是相等的

通过这点我们就可以对是否为此类的链表进行判断。

再者我们发现，如果是两个链表，按照“顺序”，第一个相等的就是相交节点

那么我们要怎么让两个节点的比较值相对整个表是一样的，因为有长短不一的表

如果从首节点开始相互比较，那他们永远都不会相等，所以我们要做到同步比较

通过计算两表的长度，让较长的表提前向前走差值步，再进行比较，当第一次比较相等时，那就是相交节点！

注意要点

在遍历尾节点时，可以顺便计算链表长度
对于长表的定义，我们可以用指针替代，然后再用各自对应的长度比较，再进行长表指针的定义，这样就可以节省掉很多if else语句。

附源代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *curA=headA;
    struct ListNode *curB=headB;
    int lenA=1,lenB=1;  //链表的长度至少为1
    while(curA->next)   //计算链表A的长度及尾节点
    {
        lenA++; //顺便计算表长
        curA=curA->next;
    }
    while(curB->next)
    {
        lenB++;
        curB=curB->next;
    }
    if(curA!=curB)
    {
        return NULL;    //两边的为节点不相同，那根本不是相交链表
    }

    int gap=abs(lenA-lenB); //abs为取绝对值
    struct ListNode *longlist=headA;    //假设A为长节点，这里我们利用替身来表示长表
    struct ListNode *shortlist=headB;   //就可以节省很多判断语句
    if(lenB>lenA)                       //若B长，侧替换
    {
        longlist=headB;
        shortlist=headA;
    }
    while(gap--)
    {
        longlist=longlist->next;    //先走差值步
    }
    while(longlist!=shortlist)  //不等于则同时向前遍历，直到相等
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;    //返回第一个相等值
}