leetcode每日一練：鏈表OJ題

鏈表經典算法OJ題

1.1 移除鏈表元素

題目要求：

給你一個鏈表的頭節點?head?和一個整數?val?，請你刪除鏈表中所有滿足?Node.val == val?的節點，并返回?新的頭節點?。

示例 1：
輸入：head = [1,2,6,3,4,5,6], val = 6
輸出：[1,2,3,4,5]
示例 2：
輸入：head = [], val = 1
輸出：[]
示例 3：
輸入：head = [7,7,7,7], val = 7
輸出：[]

解題思路：

思路1：

定義兩個指針，一個指向當前節點，一個指向當前節點的下一個節點，如果下一個節點是要刪除的節點就將當前節點的next存儲下一個節點的再下一個節點的地址，然后free那個節點。知道遍歷完原鏈表，該思路是改變原鏈表。

思路2：

建立一個新的鏈表，遍歷原鏈表，將原鏈表中的非刪除節點給新的鏈表，遍歷結束后新鏈表中沒有要刪除節點。

struct ListNode{int val;struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* Newhead, * NewTail;//一個頭鏈表，一個鏈表尾部Newhead = NewTail = NULL;//遍歷原鏈表struct ListNode* pcur = head;while (pcur){if (pcur->val != val){if (Newhead == NULL){Newhead = NewTail = pcur;}else{NewTail->next = pcur;NewTail = NewTail->next;}}pcur = pcur->next;}//如果要刪除值在原鏈表為節點,新鏈表的尾節點就不會指向NULL，所以這里要判斷if (NewTail){NewTail->next = NULL;}return Newhead;
}

1.2 反轉鏈表

題目要求：

給你單鏈表的頭節點?head?，請你反轉鏈表，并返回反轉后的鏈表。

示例 1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
示例 2：
輸入：head = [1,2]
輸出：[2,1]
示例 3：
輸入：head = []
輸出：[]
進階：鏈表可以選用迭代或遞歸方式完成反轉。你能否用兩種方法解決這道題？

解題思路：

可以定義三個新的節點類型的指針變量n1、n2、n3。然后就可以使用這三個指針來反轉鏈表。首先n1初始化為NULL，n2初始化為head鏈表頭結點，n3則是head頭結點的下一個節點。然后循環n2->next = n1，?n1 = n2，?n2 = n3，n3 = n3->next。循環往復就完成了反轉鏈表的操作。

typedef struct ListNode{int val;struct ListNode *next;
}*pList;//反轉鏈表函數實現
pList reverselist(pList head){if (head == NULL){return NULL;}pList n1, n2, n3;n1 = NULL, n2 = head, n3 = head->next;while (n2){n2->next = n1;n1 = n2;n2 = n3;if(n3)//如果n3為NULL就不再向后訪問了n3 = n3->next;}return n1;
}//以下調用上面函數的main是我自己寫的，可以供大家參考
int main()
{//創建鏈表struct ListNode* phead, *pTail, *p;phead = pTail = NULL;int n = 0;printf("請輸入要創建鏈表節點個數:>");scanf("%d", &n);int i = 0;for (i = 0; i < n; i++){p = (pList)malloc(sizeof(struct ListNode));printf("請輸入第%d個節點的值:>", i + 1);scanf("%d", &(p->val));p->next = NULL;if (phead == NULL){phead = p;pTail = phead;}else{pTail->next = p;pTail = pTail->next;}}//調用反轉鏈表函數pList Newhead = reverselist(phead);if (Newhead == NULL){perror("reverselist");return;}phead = Newhead;//打印鏈表節點數據while (Newhead){printf("%d->", Newhead->val);Newhead = Newhead->next;}printf("NULL\n");i = 1;Newhead = phead;//銷毀鏈表while (Newhead){phead = phead->next;free(Newhead);Newhead = phead;printf("已釋放第%d條節點\n", i);i++;}return 0;
}

1.3 合并兩個有序鏈表

題目要求：

將兩個升序鏈表合并為一個新的?升序?鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。?

示例 1：
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：
輸入：l1 = [], l2 = []
輸出：[]
示例 3：
輸入：l1 = [], l2 = [0]
輸出：[0]

解題思路：

定義兩個新的節點指針，一個頭節點，一個尾結點。比較兩個原鏈表當前節點的數據大小，然后插入新的鏈表，知道插完為止

typedef struct ListNode {int val;struct ListNode* next;
}*pList;
//合并兩個有序鏈表函數實現
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if (list1 == NULL){return list2;}if (list2 == NULL){return list1;}struct ListNode* cur1, *cur2;cur1 = list1, cur2 = list2;struct ListNode* phead, * pTail;phead = pTail = (struct ListNode*)malloc(sizeof(struct ListNode));while (cur1 && cur2) {if (cur1->val < cur2->val){pTail->next = cur1;pTail = pTail->next;cur1 = cur1->next;}else{pTail->next = cur2;pTail = pTail->next;cur2 = cur2->next;}}if (cur1) {pTail->next = cur1;}if (cur2) {pTail->next = cur2;}struct ListNode* retList = phead->next;free(phead);return retList;
}
//以下創建鏈表調用函數的代碼是自己寫的，只為調用上面函數，不是鏈表規范創建。僅供參考
int main()
{struct ListNode* phead1, pTail1, p1;struct ListNode* phead2, pTail2, p2;phead1 = pTail1 = NULL;phead2 = pTail2 = NULL;int n = 0;printf("請輸入要創建p1和p2鏈表節點個數:>");scanf("%d", &n);int i = 0;for (i = 0; i < n; i++){p1 = (pList)malloc(sizeof(struct ListNode));p2 = (pList)malloc(sizeof(struct ListNode));printf("請輸入p1鏈表第%d個節點的值:>", i + 1);scanf("%d", &(p1->val));printf("請輸入p2鏈表第%d個節點的值:>", i + 1);scanf("%d", &(p2->val));p1->next = NULL;p2->next = NULL;if (phead1 == NULL && phead2 == NULL){phead1 = p1;pTail1 = phead1;phead2 = p2;pTail2 = phead2;}else{pTail1->next = p1;pTail1 = pTail1->next;pTail2->next = p2;pTail2 = pTail2->next;}}pList Newhead = mergeTwoLists(phead1,phead2);if (Newhead == NULL){perror("reverselist");return;}pList phead = Newhead;while (Newhead){printf("%d->", Newhead->val);Newhead = Newhead->next;}printf("NULL\n");i = 1;Newhead = phead;while (Newhead){phead = phead->next;free(Newhead);Newhead = phead;printf("已釋放第%d條節點\n", i);i++;}return 0;
}

1.4 鏈表的中間節點

題目要求：

給你單鏈表的頭結點?head?，請你找出并返回鏈表的中間結點。

如果有兩個中間結點，則返回第二個中間結點。

示例 1：
輸入：head = [1,2,3,4,5]
輸出：[3,4,5]
解釋：鏈表只有一個中間結點，值為 3 。
示例 2：
輸入：head = [1,2,3,4,5,6]
輸出：[4,5,6]
解釋：該鏈表有兩個中間結點，值分別為 3 和 4 ，返回第二個結點。

解題思路：

快慢指針：使用快慢指針來遍歷鏈表，慢指針每次走一步，快指針每次走兩步，當快指針走到最后慢指針剛好走到中間節點。因為快指針是慢指針的2倍。所以快指針從起點到終點時慢指針就是這個路程的一半，是中點。

typedef struct ListNode{int val;struct ListNode* next;
}*pList;
//函數實現
struct ListNode* middleNode(struct ListNode* head) {if (head == NULL){return NULL;}struct ListNode* slow, *fast;slow = fast = head;//節點數可能是奇數個也可能是偶數個，所以要兩種判斷while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;
}

1.5 環形鏈表的約瑟夫問題

著名的Josephus問題

據說著名的歷史學家 Josephus有過以下的故事：故事據說發生在古羅馬時期，在羅馬人占領喬塔帕特后，39個猶太人與約瑟夫及他的朋友躲到一個洞中，他們寧愿死也不要被敵人抓到，于是約定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下1個人重新報數，直到所有人都自殺身亡為止。

然而Josephus 和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。

題目要求：

編號為 1?到 n?的 n?個人圍成一圈。從編號為 1?的人開始報數，報到 m?的人離開。

下一個人繼續從 1?開始報數。

n-1 輪結束以后，只剩下一個人，問最后留下的這個人編號是多少？

數據范圍：?1≤𝑛,𝑚≤100001≤n,m≤10000

進階：空間復雜度?𝑂(1)O(1)，時間復雜度?𝑂(𝑛)O(n)

示例1

輸入：
5,2     
復制返回值：
3    
復制說明：
開始5個人 1，2，3，4，5 ，從1開始報數，1->1，2->2編號為2的人離開
1，3，4，5，從3開始報數，3->1，4->2編號為4的人離開
1，3，5，從5開始報數，5->1，1->2編號為1的人離開
3，5，從3開始報數，3->1，5->2編號為5的人離開
最后留下人的編號是3      
示例2

輸入：
1,1
返回值：
1

typedef struct ListNode ListNode;創建一個節點并返回
ListNode* ListBuyNode(int val)
{ListNode* ret = (ListNode*)malloc(sizeof(ListNode));if(ret==NULL){perror("malloc");return NULL;}ret->val = val;ret->next = NULL;return ret;
}
//創建一個環形鏈表并返回
ListNode* CreatNode(int n)
{ListNode* phead = ListBuyNode(1);ListNode* pTail = phead;int i = 0;for(i=2;i<=n;i++){pTail->next = ListBuyNode(i);pTail = pTail->next;}pTail->next = phead;//將鏈表循環return pTail;
}int ysf(int n, int m ) {// write code hereListNode* prev = CreatNode(n);ListNode* cur = prev->next;int count = 1;//遍歷判斷while(cur->next!=cur){if(count == m){prev->next = cur->next;free(cur);cur = prev->next;count = 1;}else{prev = cur;cur = cur->next;count++;}}return cur->val;
}

1.6 分隔鏈表

題目要求：

給你一個鏈表的頭節點?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]

解題思路：

大小鏈表：我們可以創建兩個新的鏈表，為大小鏈表。遍歷原鏈表。大于等于x的節點連接在大鏈表，小于x的節點連接在小鏈表。最后將大鏈表的頭結點連接在小鏈表的尾結點。返回小鏈表的頭結點

typedef struct ListNode {int val;struct ListNode* next;
}*pList;//分隔鏈表的函數實現
struct ListNode* partition(struct ListNode* head, int x) {if (head == NULL){return NULL;}struct ListNode* lessHead, * lessTail;struct ListNode* greaterHead, * greaterTail;//定義哨兵位lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* pcur = head;//用來遍歷原鏈表//分隔操作while (pcur){if (pcur->val >= x){greaterTail->next = pcur;greaterTail = greaterTail->next;}else{lessTail->next = pcur;lessTail = lessTail->next;}pcur = pcur->next;}//將大小鏈表連接起來lessTail->next = greaterHead->next;if(greaterTail)greaterTail->next = NULL;//釋放哨兵位free(greaterHead);struct ListNode* retList = lessHead->next;free(lessHead);//返回頭結點return retList;
}
int main()
{pList phead, pTail, p;phead = pTail = NULL;int n = 0;printf("請輸入要創建鏈表節點個數:>");scanf("%d", &n);int i = 0;for (i = 0; i < n; i++){p = (pList)malloc(sizeof(struct ListNode));printf("請輸入第%d個節點的值:>", i + 1);scanf("%d", &(p->val));p->next = NULL;if (phead == NULL){phead = p;pTail = phead;}else{pTail->next = p;pTail = pTail->next;}}pList Newhead = partition(phead, 3);if (Newhead == NULL){perror("reverselist");return;}phead = Newhead;while (Newhead){printf("%d->", Newhead->val);Newhead = Newhead->next;}printf("NULL\n");i = 1;Newhead = phead;while (Newhead){phead = phead->next;free(Newhead);Newhead = phead;printf("已釋放第%d條節點\n", i);i++;}return 0;
}