【Leetcode -234.回文链表 -160.相交链表】

YoungMLet

发布于 2024-03-01 09:32:15

1060

发布于 2024-03-01 09:32:15

文章被收录于专栏：C++/Linux

Leetcode -234.回文链表

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

示例 1：输入：head = [1, 2, 2, 1] 输出：true

示例 2：输入：head = [1, 2] 输出：false

提示：链表中节点数目在范围[1, 10^5] 内 0 <= Node.val <= 9

我们的思路是，把链表分为两个部分，以中间的结点为分界线，分为前半部分和后半部分，如果有两个中间结点，以第一个中间结点为标准；以1->2->2->1->NULL为例，如图：

然后反转以mid为中间结点的后半部分的链表，即反转以mid->next为头的链表；如下图：

反转完成的链表：

注意反转过程中改变了链表的结构，应该在返回前把反转的部分反转回来；下面看代码以及注释：

		//找到链表前半部分的函数
		struct ListNode* SLFindMid(struct ListNode* head)
		{
		    struct ListNode* slow = head, * fast = head;
		    while (fast->next && fast->next->next)
		    {
		        slow = slow->next;
		        fast = fast->next->next;
		    }
		    return slow;
		}
		
		//反转链表的函数
		struct ListNode* SLReverse(struct ListNode* head)
		{
		    struct ListNode* curr = head, * prev = NULL;
		    while (curr)
		    {
		        struct ListNode* next = curr->next;
		        curr->next = prev;
		        prev = curr;
		        curr = next;
		    }
		    return prev;
		}
		
		bool isPalindrome(struct ListNode* head)
		{
		    //通过SLFindMid函数找到链表的前半部分，返回的是前半部分的尾指针
		    //SLReverse函数反转后半部分的链表
		    struct ListNode* mid = SLFindMid(head);
		    struct ListNode* reverse = SLReverse(mid->next);
		
		    //p1从头开始，p2从反转后后半部分链表的头开始
		    struct ListNode* p1 = head;
		    struct ListNode* p2 = reverse;
		
		    //p1和p2通过迭代比较，当p2不为空则继续比较，p2为空说明前半部分和后半部分比较完了
		    while (p2)
		    {
		        if (p1->val == p2->val)
		        {
		            p1 = p1->next;
		            p2 = p2->next;
		        }
		
		        //如果比较途中遇到不相等，返回false
		        else
		        {
		        	//把反转的后半部分反转回来，保持链表为原来的结构
		        	SLReverse(reverse);
		            return false;
		        }
		    }
		
		    //最后把反转的后半部分反转回来，保持链表为原来的结构
		    SLReverse(reverse);
		    return true;
		}

Leetcode -160.相交链表

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

我们的思路是，分别计算两个链表的长度，再计算它们的差值gap，然后让长的那一个链表先走gap步，使它们从长度相同的结点出发比较；

		struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
		{
		    //从头遍历两个链表，计算它们的长度
		    struct ListNode* tailA = headA, * tailB = headB;
		    int lenA = 0, lenB = 0;
		    while (tailA)
		    {
		        lenA++;
		        tailA = tailA->next;
		    }
		    while (tailB)
		    {
		        lenB++;
		        tailB = tailB->next;
		    }
		
		    //gap计算它们的差值，abs为取绝对值
		    int gap = abs(lenA - lenB);
		
		    //假设A链表为长的那一个链表，B为短的链表
		    struct ListNode* longlist = headA, * shortlist = headB;
		
		    //判断A和B谁是比较长的链表
		    if (lenA < lenB)
		    {
		        longlist = headB;
		        shortlist = headA;
		    }
		
		    //让长的链表先走gap步
		    while (gap--)
		    {
		        longlist = longlist->next;
		    }
		
		    //两个链表从长度相同的结点出发比较
		    while (longlist != shortlist)
		    {
		        longlist = longlist->next;
		        shortlist = shortlist->next;
		    }
		
		    return longlist;
		}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-02-29，如有侵权请联系 cloudcommunity@tencent.com 删除

函数