0


链表OJ练习(2)

一、分割链表

题目介绍:

思路:创建两个链表,ghead尾插大于x的节点,lhead尾插小于x的节点。先遍历链表。最后将ghead尾插到lhead后面,将大小链表链接。

      我们需要在创建两个链表指针,指向两个链表的头节点,用这两个指针标记lhead和ghead的尾结点,方便与尾插。

注:极端边界场景:所有值都小于x; 所有值都大于x; 空链表。

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

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x)
    {
        ListNode* gtail, * ghead, * ltail, * lhead;
        gtail = ghead = (struct ListNode*)malloc(sizeof(struct ListNode));
        ltail = lhead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        while (cur)
        {
            if (cur->val < x)
            {
                ltail->next = cur;
                ltail = ltail->next;
            }
            else
            {
                gtail->next = cur;
                gtail = gtail->next;
            }
            cur = cur->next;
        }
        ltail->next = ghead->next;
        gtail->next = NULL;
        struct ListNode* newhead = lhead->next;
        free(lhead);
        free(ghead);
        return newhead;
    }
};

二、回文链表

题目介绍:

思路:先找到中间节点,可以利用快慢指针找到中间节点,然后将中间节点后面的节点翻转,在和中间节点前面的链表依次比较,如果全部相同则是回文链表否则不是。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
//struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* falst;
    struct ListNode* slow;
    falst = head;
    slow = head;
    while (falst && falst->next)
    {
        slow = slow->next;
        falst = falst->next->next;
    }
    return slow;
}
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;
}

class PalindromeList
{
public:
    bool chkPalindrome(ListNode* head)
    {
        //找到中间节点,将中间节点后面的链表翻转,有第一个和中间节点比较,并依次后移,若全部相同,则为回文链表,反之不是。
        struct ListNode* mid = middleNode(head);
        struct ListNode* rmid = reverseList(mid);
        while (rmid && mid)
        {
            if (rmid->val != head->val)
            {
                return false;
            }
            head = head->next;
            rmid = rmid->next;
        }
        return true;
    }

};

三、找公共点

题目介绍:

思路:先遍历两个链表,计算出两个链表的长度,让后计算出两个链表的长度差k,将长的链表先往前走k步,然后将两个链表指针同时后移,找到第一个相同的节点就是相交节点。

注:需要考虑到空链表,给链表判空,若空headA和headB其中一个为空返回NULL。

/**
 * 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;
   int lenB = 1;
   if(headA==NULL||headB==NULL)
   {
       return NULL;
   }
   while (curA->next)
   {
       curA = curA->next;
       lenA++;
   }
   while (curB->next)
   {
       curB = curB->next;
       lenB++;
   }
   if (curA != curB)  //没有交点
   {
       return false;
   }
   int gap = abs(lenA - lenB);
   struct ListNode* falst = headA;
   struct ListNode* slow = headB;
   if (lenA < lenB)
   {
       falst = headB;
       slow = headA;
   }
   while (gap--)
   {
       falst = falst->next;
   }
   while (slow != falst)
   {
       slow = slow->next;
       falst = falst->next;
   }
   return slow;
}

四、判断是否是环形链表

题目介绍:

思路:还是利用快慢指针,当慢指针往前走一步,快指针往前走两步,在一个环中,每次他们的距离就减少一,如果有环,就一定能追上。如果没追上则没有环。

用快指针遍历。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) 
{
    struct ListNode *falst=head;
    struct ListNode *slow=head;
    while(falst&&falst->next)
    {
        falst=falst->next->next;
        slow=slow->next;
        if(falst==slow)
        {
            return true;
        }

    }
    return false;
}

五、寻找环形链表的入环节点

题目描述:

思路1:假设链表带环,头节点head与入环节点的距离为L,入环节点与相遇点的距离为D,环的大小为C,如下图:

fast从头节点到相遇点:L + D + kC,其中k为正整数,表示在快慢指针相遇前fast所走圈数

slow从头节点到相遇点:L + D

又由于fast每次走两步,slow每次走一步,以上二式可以建立起联系:

L + D + kC = 2 * (L + D)

L = kC - D = (k - 1) * C + C - D

所以可以得出结论:一个指针从相遇点开始走,一个指针从链表头开始走,则这两个指针一定会在入环节点处相遇。

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast=head, *slow=head;
    while(fast && fast->next)
    {
        fast=fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            //找相遇点meetNode
            struct ListNode* meetNode = fast;
            //相遇点可能就是入环节点
            if(meetNode == head)
                return head;
            //meetNode和head开始每次走一步,直到相遇
            while(head && meetNode)
            {
                meetNode = meetNode->next;
                head = head->next;
                //当相遇时即为入环节点
                if(meetNode == head)
                   return meetNode;
            }
        }
    }
    return NULL;
}

思路2:我们可以在相遇点将链表断开,找到如节点就相当于找到两个链表的交点。

找两个链表的交点我们可以参考题目三

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode *curA=headA;
    struct ListNode *curB=headB;
    int lenA=1;
    int lenB=1;
    while(curA->next)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB=curB->next;
        lenB++;
    }
    if(curA!=curB)  //没有交点
    {
        return false;
    }
    int gap=abs(lenA-lenB);
    struct ListNode *falst=headA;
    struct ListNode *slow=headB;
    if(lenA<lenB)
    {
        falst=headB;
        slow=headA;
    }
    while(gap--)
    {
        falst=falst->next;
    }
    while(slow!=falst)
    {
        slow=slow->next;
        falst=falst->next;
    }
    return slow;
}
struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode *fast=head;
    struct ListNode *slow=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)  //相遇了
        {
            struct ListNode *meet=slow;  //将环断开
            struct ListNode *newhead=meet->next;
            meet->next=NULL;
            return getIntersectionNode(head,newhead); //找两个链表的交点
        }
    }
    return NULL;
}
标签: 链表 数据结构

本文转载自: https://blog.csdn.net/m0_69323023/article/details/132642843
版权归原作者 #欲速则不达# 所有, 如有侵权,请联系我们删除。

“链表OJ练习(2)”的评论:

还没有评论