一、合并兩個有序鏈表

1、題目描述?

https://leetcode.cn/problems/merge-two-sorted-lists

?2、算法分析

這道題和之前的合并兩個有序數組的思路很像，創建空鏈表即可，可以很輕松地寫出如下代碼。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//創建空鏈表ListNode* newHead = NULL;ListNode* newTail = NULL;ListNode* l1 = list1;ListNode* l2 = list2;while(l1 && l2){if(l1->val >= l2->val){//l2尾插到新鏈表中if(newHead == NULL){newHead = newTail = l2;}else{//鏈表非空newTail->next = l2;newTail = newTail->next;}l2 = l2->next;}else{//l1尾插到新鏈表中if(newHead == NULL){newHead = newTail = l1;}else{newTail->next = l1;newTail = newTail->next;}l1 = l1->next;}}//要么l1為空，要么l2為空if(l1)newTail->next = l1;if(l2)newTail->next = l2;return newHead;
}

雖然這個代碼可以運行通過，但有個很嚴重的問題——太過冗余！雖然我們可以將尾插的代碼封裝成函數來解決，但是這里我提供一個更好的方法。導致代碼冗余的根本原因就在于我們創建的是一個空的新鏈表，因此要進行if…else…語句判斷，那我直接一開始向系統申請一塊空間，創建新的非空的鏈表不就可以了。至于新的非空鏈表的val值是什么，我們不用在乎，因為這個非空鏈表起的是一個占位置的作用（在后續的鏈表學習中，這種起到占位置作用的節點，我們稱之為“哨兵位”）。所有節點按題目要求尾插完成后，新鏈表就是如下圖所示的樣子：

這里要注意，我們此時不能返回newHead，而是應該返回newHead的下一個節點才對。并且我們向系統申請的空間在結束后也要釋放（雖然在OJ平臺上是否釋放不會影響整體程序，但還是要養成好習慣~）

3、參考代碼

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//創建非空鏈表ListNode* newHead, *newTail;newHead = newTail = (ListNode*)malloc(sizeof(ListNode));ListNode* l1 = list1;ListNode* l2 = list2;while(l1 && l2){if(l1->val >= l2->val){//l2尾插到新鏈表中newTail->next = l2;newTail = newTail->next;l2 = l2->next;}else{//l1尾插到新鏈表中newTail->next = l1;newTail = newTail->next;l1 = l1->next;}}//要么l1為空，要么l2為空if(l1){newTail->next = l1;}if(l2){newTail->next = l2;}ListNode* retHead = newHead->next;free(newHead);newHead = NULL;return retHead;
}

二、鏈表的回文結構

1、題目描述

https://www.nowcoder.com/share/jump/1753713495724

2、算法分析?

提到回文結構，我們會很自然地想到去定義兩個指針，一個指向頭，一個指向尾，比較兩個值是否相等，再讓頭指針往后走，尾指針往前走。但這道題是一個單向鏈表，尾指針沒有辦法往前走。所以這個方法不太行。那我們又想到，找到中間位置，從中間位置向兩邊走，但是同理還是不行。既然在鏈表中我們無法判斷是否回文，那我們創建一個新數組，把鏈表的值遍歷到新數組中，在數組中判斷回文結構不就可以了嗎？這里注意，題目中明確指出空間復雜度為O(1)，因此這里我們創建一個定長數組arr[900]即可。（題目說了保證鏈表長度小于等于900）

根據上述思路，給出參考代碼如下：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList 
{
public:bool chkPalindrome(ListNode* A) {//創建數組int arr[900] = {0};//遍歷鏈表，將鏈表中的值保存在數組中ListNode* pcur = A;int i = 0;while(pcur){arr[i] = pcur->val;i++;pcur = pcur->next;}//判斷數組是否為回文結構int left = 0;int right = i - 1;while(left < right){if(arr[left] != arr[right]){return false;}left++;right--;}return true;}
};

但是這個方法畢竟是應試，有點“投機取巧”，所以這里給出更嚴謹、更合理的方法。

思路2：找鏈表的中間結點，將中間節點作為新的鏈表的頭結點進行反轉鏈表。

3、參考代碼

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public://找中間節點ListNode* middleNode(ListNode* head){ListNode* slow, *fast;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}//反轉鏈表ListNode* reverseList(ListNode* head){if(head == nullptr){return head;}ListNode* n1, *n2, *n3;n1 = nullptr;n2 = head;n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3){n3 = n3->next;}}return n1;}bool chkPalindrome(ListNode* A) {//找中間節點ListNode* mid = middleNode(A);//反轉中間節點之后的鏈表ListNode* right = reverseList(mid);//遍歷原鏈表和反轉之后的鏈表ListNode* left = A;while(right){if(left->val != right->val){return false;}left = left->next;right = right->next;}return true;}
};

三、相交鏈表?

1、題目描述

https://leetcode.cn/problems/intersection-of-two-linked-lists

?

2、算法分析?

思路：求兩個鏈表的長度并計算長度差，長鏈表先走長度差步，然后兩個鏈表同時往后遍歷。

3、參考代碼

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{//求兩個鏈表的長度ListNode* pa = headA;ListNode* pb = headB;int sizeA = 0, sizeB = 0;while(pa){sizeA++;pa = pa->next;}while(pb){sizeB++;pb = pb->next;}//計算長度差int gap = abs(sizeA - sizeB);//abs函數：用于求絕對值//讓長鏈表先走gap步ListNode* shortList = headA;ListNode* longList = headB;if(sizeA > sizeB){longList = headA;shortList = headB;}while(gap--){longList = longList->next;}//longList和shortList在同一起跑線while(shortList){if(longList == shortList){return longList;}shortList = shortList->next;longList = longList->next;}return NULL;
}

?