链表专项练习(三)

lovevivi

发布于 2022-11-10 14:50:00

1960

发布于 2022-11-10 14:50:00

文章被收录于专栏：萌新的日常

一、160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。自定义评测：评测系统的输入如下（你设计的程序不适用此输入）： intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0 listA - 第一个链表 listB - 第二个链表 skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被视作正确答案。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    int sumA=0;
    int sumB=0;
    struct ListNode*curA=headA;
    struct ListNode*curB=headB;
    while(curA!=NULL)//求headA的长度
    {
        sumA++;
        curA=curA->next;
    }
    while(curB!=NULL)//求headB的长度
    {
        sumB++;
        curB=curB->next;
    }
    int k=sumA>sumB?sumA-sumB:sumB-sumA;//长度差
    struct ListNode* longlist=headA;
    struct ListNode* shortlist=headB;
    if(sumB>sumA)//无论怎么变，longlist都是最长的那个
    {
        longlist=headB;
        shortlist=headA;
    }
    while(k--)//将longlist向后移长度次
    {
        longlist=longlist->next;
    }
    while(longlist!=NULL&amp;&amp;shortlist!=NULL)
    {
        if(longlist==shortlist)
        {
            return longlist;
        }
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return NULL;

}

二、面试题 02.04. 分割链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你不需要保留每个分区中各节点的初始相对位置。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode* lesshead,*lesstail;
    struct ListNode*morehead,*moretail;//都是带哨兵位的头节点
    lesshead=lesstail=(struct ListNode*)malloc(sizeof(struct ListNode));//设立四个头节点
    morehead=moretail=(struct ListNode*)malloc(sizeof(struct ListNode));//分别代表比x小的和比x大的
       morehead->next=NULL;
       lesshead->next=NULL;
       struct ListNode*cur=head;
       while(cur!=NULL)
       {
           if(cur->val<x)//如果比x小就传入lesstail中
           {
            lesstail->next=cur;
            lesstail=lesstail->next;
           }
           else
           {
               moretail->next=cur;//如果比x大就传入moretail中
               moretail=moretail->next;
           }
           cur=cur->next;
       }
       lesstail->next=morehead->next;//lesstail的尾来连接morehead的下一个
       moretail->next=NULL;//因为我们不知道此时的最后一个节点是否为原节点的最后一个 所以需要置空
       struct ListNode*prev=lesshead->next;//接收lesshead的后一个节点
       free(lesshead);
       free(morehead);
       return prev;
}

三、876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2：输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* middleNode(struct ListNode* head){
       struct ListNode*fast=head;//快慢指针 快指针一次走两步 慢指针一次走一步
       struct ListNode*slow=head;
       while(fast&amp;&amp;fast->next)
       {
           fast=fast->next->next;
           slow=slow->next;
       }
       return slow;
}

四、234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


bool isPalindrome(struct ListNode* head){
     struct ListNode*fast=head;
     struct ListNode*slow=head;
     while(fast&amp;&amp;fast->next)//寻找中间节点
     {
         fast=fast->next->next;
         slow=slow->next;
     }
     struct ListNode*n1=NULL;
     struct ListNode*n2=slow;
     struct ListNode*n3=slow->next;
     while(n2!=NULL)//逆置中间节点后的节点
     {
         n2->next=n1;
         n1=n2;
         n2=n3;
         if(n3!=NULL)
         {
             n3=n3->next;
         }
     }
     while(head&amp;&amp;n1)//如果从头开始的与从尾开始的都相等就是 反之就不是
     {
         if(head->val==n1->val)
         {
           head=head->next;
           n1=n1->next;
         }
         else
         {
             return false;
         }
     }
     return true;
}