[算法] leetcode单链表相关题目详解(二)

叁歲伎倆 2023-01-21 14:23 81阅读 0赞

### 目录 ###

*  1. leetcode\_21-合并两个有序链表
 *   *  解法
 *  2. leetcode\_86.-分隔链表
 *   *  解法
 *  3. leetcode\_234-回文链表
 *   *  解法
 *  4. leetcode\_160-相交链表
 *   *  解法

# 1. leetcode\_21-合并两个有序链表 #

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
    
    示例 1：
    输入：l1 = [1,2,4], l2 = [1,3,4]
    输出：[1,1,2,3,4,4]
    
    示例 2：
    输入：l1 = [], l2 = []
    输出：[]
    
    示例 3：
    输入：l1 = [], l2 = [0]
    输出：[0] 
    
    提示：
    两个链表的节点数目范围是 [0, 50]
    -100 <= Node.val <= 100
    l1 和 l2 均按 非递减顺序 排列
    
    https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/

## 解法 ##

新建一个带头的链表用于存放合并后的链表，合并两个链表时，比较两链表节点值的大小，节点值较小的放入新链表中  
  最后分析两个链表是否已经全部将元素放入新链表中，如果没有的话，则将节点依次放入新链表中, 最后返回新链表的next指针

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) 
    { 
    	if (NULL == l1)
    		return l2;
    	if (NULL == l2)
    		return l1;
    
    	struct ListNode* pNew = (struct ListNode*)malloc(sizeof(struct ListNode));
    	pNew->next = NULL;
    
    	struct ListNode* pNewL = pNew;   // 用于指向新链表的尾节点
    
    	// 将符合条件的节点插入新链表中
    	while (NULL != l1 && NULL != l2)
    	{ 
    		if (l1->val <= l2->val)
    		{ 
    			pNewL->next = l1;
    			l1 = l1->next;
    		}
    		else
    		{ 
    			pNewL->next = l2;
    			l2 = l2->next;
    		}
    
    		pNewL = pNewL->next;
    	}
    
    	// 将剩余节点依次放入新链表中
    	if (NULL != l1)
    	{ 
    		pNewL->next = l1;
    	}
    	else
    	{ 
    		pNewL->next = l2;
    	}
    
    	return pNew->next;
    }

# 2. leetcode\_86.-分隔链表 #

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
    你应当 保留 两个分区中每个节点的初始相对位置。
    
    示例 1：
    输入：head = [1,4,3,2,5,2], x = 3
    输出：[1,2,2,4,3,5]
    
    示例 2：
    输入：head = [2,1], x = 2
    输出：[1,2]
     
    提示：
    链表中节点的数目在范围 [0, 200] 内
    -100 <= Node.val <= 100
    -200 <= x <= 200
    
    leetcode: https://leetcode-cn.com/problems/partition-list/

## 解法 ##

题目要求为，按照某个数值划分链表，所以可以构造两个带头链表，分为两种情况，将大于val值和小于val值的节点分别尾插放入两个链表中，最后合并两个链表，即为所求链表。

// 构造两个带头链表，一个链表用于存储小于x的节点，一个链表用于存储大于X的节点，通过尾插的方式进行构造，不会改变原来的大小顺序
    // 最后合并两个链表
    struct ListNode* partition(struct ListNode* head, int x) 
    { 
    	if (NULL == head || NULL == head->next)
    		return head;
    
    	struct ListNode lessL;
    	lessL.next = NULL;
    	struct ListNode moreL;
    	moreL.next = NULL;
    
    	struct ListNode* lessLL = &lessL;
    	struct ListNode* moreLL = &moreL;
    
    	// 构造两个新链表
    	while (NULL != head)
    	{ 
    		if (head->val < x)
    		{ 
    			lessLL->next = head;
    			lessLL = lessLL->next;
    		}
    		else
    		{ 
    			moreLL->next = head;
    			moreLL = moreLL->next;
    		}
    
    		head = head->next;
    	}
    
    	// 拼接两链表
    	lessLL->next = moreL.next;
    	moreL.next = NULL;
    
    	return lessL.next;
    }

# 3. leetcode\_234-回文链表 #

请判断一个链表是否为回文链表。
    
    示例 1:
    输入: 1->2
    输出 : false
    
    示例 2 :
    输入 : 1->2->2->1
    输出 : true

## 解法 ##

判断一个链表是否为回文链表，因为回文链表前后对称，所以可以采用如下方法。

1.  寻找链表的中间节点
2.  翻转中间节点之后的链表
3.  逐位比较，如果发现不相同节点则不是回文结构

// 翻转链表
    struct ListNode* reverseList(struct ListNode* head)
    { 
        if (NULL == head || NULL == head->next)
            return head;
    
        struct ListNode* pPre = NULL;
        struct ListNode* pCur = head;
        struct ListNode* pNext = NULL;
    
        while (pCur != NULL)
        { 
            pNext = pCur->next;
            pCur->next = pPre;
            pPre = pCur;
            pCur = pNext;
        }
    
        return pPre;
    }
    
    // 找到链表中间节点
    struct ListNode* middleNode(struct ListNode* head)
    { 
        if (head == NULL)
            return NULL;
    
        struct ListNode* fast = head;
        struct ListNode* slow = head;
    
        // 如果链表长度为偶数，那么fast走到最后一部，fast指向刚好为NULL，停止循环
        // 如果链表长度为奇数，那么fast走到最后一步，当前节点不为空，当时fast->next->next为空，会导致出错，所以要确保fast->next不为空
        while (fast != NULL && fast->next != NULL)
        { 
            fast = fast->next->next;
            slow = slow->next;
        }
    
        return slow;
    }
    
    // 链表回文结构是关于中间对称的，所以可以先找到链表的中间节点
    // 逆置后方链表，注意比对逆置链表与前方链表是否有不相同的节点，如果有则一定不是回文结构
    bool isPalindrome(struct ListNode* head) 
    { 
        // 链表中只有一个节点的情况绝对是回文结构
        if (NULL == head || NULL == head->next)
            return true;
    
        // 如果有两个节点 则判断这两个节点是否相同，相同则是回文结构
        if (head->next->next == NULL)
        { 
            if (head->val == head->next->val)
                return true;
            else
                return false;
        }
    
        struct ListNode* pTmp = head;
    
        // 找到中间节点
        struct ListNode* pMid = middleNode(head);
    
        // 将链表拆为两部分，同时逆置一部分的链表
        struct ListNode* rear = pMid;
        pMid = NULL;
    
            // 逆置
        rear = reverseList(rear);
    
        // 比较逆置的两部分链表
        while (NULL != rear && NULL != pTmp)
        { 
            if (rear->val != pTmp->val)
                return false;
    
            rear = rear->next;
            pTmp = pTmp->next;
        }
    
        return true;
    }

# 4. leetcode\_160-相交链表 #

编写一个程序，找到两个单链表相交的起始节点。
    
    	如下面的两个链表：
    	在节点 c1 开始相交。
    
    	示例 1：
    	输入：intersectVal = 8, listA = [4, 1, 8, 4, 5], listB = [5, 0, 1, 8, 4, 5], skipA = 2, skipB = 3
    	输出：Reference of the node with value = 8
    	输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为[4, 1, 8, 4, 5]，链表 B 为[5, 0, 1, 8, 4, 5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
    
    	示例 2：
    	输入：intersectVal = 2, listA = [0, 9, 1, 2, 4], listB = [3, 2, 4], skipA = 3, skipB = 1
    	输出：Reference of the node with value = 2
    	输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为[0, 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。

## 解法 ##

两链表相交一共分3种情况：Y V L 三种形态，因为在上述结构中，两个链表都相交到了一点，并且相交后结束节点相同，  
  如何判断两个链表是否相交，只需要检测两个链表的最后一个节点是否相同，如果相同，则链表必定相交

**思路：**  
  1.判断两链表是否相交  
  2.如果相交则求出交点：计算两链表长度，让较长的链表先移动 长-短的长度，之后两链表同时移动，如果俩节点地址相同则相交  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]

struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
    { 
       if (NULL == headA || NULL == headB)
       	return NULL;
    
       struct ListNode* pTmpA = headA;
       struct ListNode* pTmpB = headB;
    
       int lenA = 0;
       int lenB = 0;
    
       // 1.判断两链表是否相交
       while (pTmpA != NULL)
       { 
       	pTmpA = pTmpA->next;
       	lenA++;
       }
       	
       while (pTmpB != NULL)
       { 
       	pTmpB = pTmpB->next;
       	lenB++;
       }
    
       if (pTmpA != pTmpB)
       	return NULL;
    
       // 2.求交点
       	// 先计算两链表长度差
       int distance = lenA - lenB;
       	// 移动其中一个链表指针到指定位置
       pTmpA = headA;
       pTmpB = headB;
       if (distance < 0)
       { 
       	while (distance++ < 0)
       		pTmpB = pTmpB->next;
       }
       else
       { 
       	while (distance-- > 0)
       		pTmpA = pTmpA->next;
       }
    
       // 两指针同时移动，判断地址是否相同
       while (pTmpA != NULL && pTmpB != NULL)
       { 
       	if (pTmpA == pTmpB)
       		break;
       	pTmpA = pTmpA->next;
       	pTmpB = pTmpB->next;
       }
    
       return pTmpA;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/32f058c4a0a444c09d63d20113215372.png