leetcode - 交換鏈表中的節(jié)點

題意

給你鏈表的頭節(jié)點 head 和一個整數(shù) k 。

交換 鏈表正數(shù)第 k 個節(jié)點和倒數(shù)第 k 個節(jié)點的值后，返回鏈表的頭節(jié)點（鏈表 從 1 開始索引）。

示例

示例 1：

輸入：head =?[1,2,3,4,5], k = 2
輸出：[1,4,3,2,5]

示例 2：

輸入：head =?[7,9,6,6,7,8,3,0,9,5], k = 5
輸出：[7,9,6,6,8,7,3,0,9,5]

示例 3：

輸入：head =?[1], k = 1
輸出：[1]

示例 4：

輸入：head =?[1,2], k = 1
輸出：[2,1]

示例 5：

輸入：head =?[1,2,3], k = 2
輸出：[1,2,3]

提示

• 鏈表中節(jié)點的數(shù)目是 n

• 1 <= k <= n <= 105

• 0 <= Node.val <= 100

出處

鏈接：https://leetcode-cn.com/problems/swapping-nodes-in-a-linked-list

思路

這題常規(guī)的做法是，找到第 k 個節(jié)點的上一個節(jié)點，然后將其 next 指向倒數(shù)第 k 個節(jié)點的，再將倒數(shù)第 k 個節(jié)點的 next 指向第 k 個節(jié)點的 next，然后將倒數(shù)第 k + 1 節(jié)點的 next 指向第 k 個節(jié)點，第 k 個節(jié)點的 next 節(jié)點指向倒數(shù)第 k 個節(jié)點的 next 節(jié)點。是不是有點繞，我倒是有個不成熟的想法，也試著去提交了下，發(fā)現(xiàn)能過。就是我把所以的 val 值取出來轉(zhuǎn)數(shù)組，在 js 中，單純的同類型數(shù)組，它在內(nèi)存中是連續(xù)的，所以其訪問復(fù)雜度是 O(1),所以我們把生成的數(shù)組的第（k - 1）個 和 數(shù)組的長度減去 k 的那位交換。最后我們構(gòu)造一個新的鏈表返回，當(dāng)然啦，后面筆者比較菜用了兩次遍歷去構(gòu)造這個鏈表然后返回。

代碼

/**
?*?@param?{ListNode}?head
?*?@param?{number}?k
?*?@return?{ListNode}
?*/
const?swapNodes?=?function?(head,?k)?{
??const?arr?=?[];
??while?(head.next)?{
????arr.push(head.val);
????head?=?head.next;
??}
??head?&&?arr.push(head.val);
??let?tmp?=?arr[k?-?1];
??arr[k?-?1]?=?arr[arr.length?-?k];
??arr[arr.length?-?k]?=?tmp;
??const?res?=?[];
??for?(let?i?=?0;?i?????const?node?=?new?ListNode(arr[i]);
????res.push(node);
??}
??for?(let?i?=?0;?i?1;?i++)?{
????res[i].next?=?res[i?+?1];
??}
??return?res[0];
};

export?default?swapNodes;

測試

import?ListNode?from?'../../code/base/list-node';
import?swapNodes?from?'../../code/leetcode/1721';

describe('test?function?swapNodes:?',?()?=>?{
??test('test?case?head?=?[1,2,3,4,5],?k?=?2',?()?=>?{
????const?before?=?[1,?2,?3,?4,?5];
????const?res_before?=?[];
????for?(let?i?=?0;?i???????const?node?=?new?ListNode(before[i]);
??????res_before.push(node);
????}
????for?(let?i?=?0;?i?1;?i++)?{
??????res_before[i].next?=?res_before[i?+?1];
????}
????const?after?=?[1,?4,?3,?2,?5];
????const?res_after?=?[];
????for?(let?i?=?0;?i???????const?node?=?new?ListNode(after[i]);
??????res_after.push(node);
????}
????for?(let?i?=?0;?i?1;?i++)?{
??????res_after[i].next?=?res_after[i?+?1];
????}
????const?res?=?swapNodes(res_before[0],?2);
????expect(res).toEqual(res_after[0]);
??});
});

思考

• 請讀者思考，用樓上提到的常規(guī)解法去求解

• 請讀者思考，如果在筆者的基礎(chǔ)上，進(jìn)一步優(yōu)化代碼

哈哈哈，挖坑不填坑。。。

說明

本文首發(fā)于 GitHub 倉庫https://github.com/ataola/coding，線上閱讀地址：https://zhengjiangtao.cn/coding/，轉(zhuǎn)載請注明出處，謝謝！