LeetCode --- 链表相关oj题 -- 2_现有一链表的头指针listnode *phead

目录

一.链表分割

思路：

二.链表的回文结构：

 思路：

 三.相交链表（160）

思路：

---

一.链表分割

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路：

思路：找到比x大的值就尾插到greaterhead的链表中
           找到比x小的值就尾插到lesshead的链表中 

           到最后再让lesstail->next=greaterhead->next;

                             greatertail->next=NULL;

//结构体
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
 
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        ListNode* lesshead=(ListNode*)malloc(sizeof(ListNode));
        ListNode* lesstail=lesshead;
        lesstail->next=NULL;
        
        ListNode* greaterhead=(ListNode*)malloc(sizeof(ListNode));
        ListNode* greatertail=greaterhead;
        greatertail->next=NULL;
            //思路：找到比x大的值就尾插到greaterhead的链表中
            //找到比x小的值就尾插到lesshead的链表中
        ListNode* cur=pHead;
        while(cur)
        {
            if(cur->val<x)
            {
                lesstail->next=cur;
                lesstail=cur;
            }
            else
            {
                greatertail->next=cur;
                greatertail=cur;
            }
            cur=cur->next;
        }
        lesstail->next=greaterhead->next;
        greatertail->next=NULL;
        ListNode* list=lesshead->next;
        //malloc申请的空间不使用了，要记得释放掉
        free(lesshead);
        free(greaterhead);
        return list;
    }
};

二.链表的回文结构：

描述：

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

 思路：

第一步：找到原链表的中间结点（mid）

第二步：逆置原链表的后半部分结点

第三步：然后把原链表的前一半和逆置后的那半个原链表的数据来进行比较，一直到某个到空为止，如果一直到达空之前，这2个部分都是相同的，那么此链表就是回文结构了

如果在这个过程中有一个位置的值不相同，那么就不是回文结构了。

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        //第一步就是找到链表的中间结点
        ListNode* slow=A;
        ListNode* fast=A;
        while(fast&&fast->next)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        ListNode* mid=slow;
        //然后逆置链表的后半部分
        ListNode* prev=NULL;
        ListNode* cur=mid;
        ListNode* next=mid;
        while(cur)
        {
            next=cur->next;
            cur->next=prev;
            prev=cur;
            cur=next;
        }
        ListNode* curA=A;
        ListNode* curM=prev;
        //然后把原链表和逆置后的那半个原链表的数据来进行比较，一直到某个到空为止
        while(curA&&curM)
        {
            if(curA->val!=curM->val)
                return false;
            else
            {
                curA=curA->next;
                curM=curM->next;
            }
        }
        return true;
    }
};

 三.相交链表（160）

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists

思路：

 1：先都分别遍历一遍这2个链表，并且分别计算处它们各自的结点个数

 2：这里要判断一下，是否相交，如果不相交就直接返回NULL，就可以了

      判断是否会相交只需要去比较2个链表最后的那个结点是否相同，

      相同则一定相交，不相同则一定不相交

 3：然后让长的链表先去走长度差步

 4：然后让2个链表同时走，开始对2个链表的结点进行比较，第一个相同地址的结点就是我们所求的交点。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    //先遍历一遍这2个链表，分别计算它们的结点个数
    struct ListNode* taila=headA;
    int sizea=1;
    while(taila->next)
    {
        taila=taila->next;
        sizea++;
    }
    struct ListNode* tailb=headB;
    int sizeb=1;
    while(tailb->next)
    {
        tailb=tailb->next;
        sizeb++;
    }
    //这里要判断一下，是否相交，如果不相交就直接返回NULL，就可以了
    //判断是否会相交只需要去比较2个链表最后的那个结点是否相同，
    //相同则一定相交，不相同则一定不相交
    if(taila!=tailb)
    {
        return NULL;
    }
    //计算2个链表的结点个数的差值（长度差）
    int gap=abs(sizea-sizeb);
    //abs是取绝对值的意思 它的头文件是 #include<stdlib.h>
    struct ListNode* shortlist=headA;
    struct ListNode* longlist=headB;
    //这里也只是默认headA短，headB长，下面还会进行进一步的判断的
    if(sizea>sizeb)
    {
        shortlist=headB;
        longlist=headA;
    }
    //长的链表要先走差距步 gap步
    while(gap--)
    {
        longlist=longlist->next;
    }
    //开始比较，看是否是回文结构
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
 
}