?LeetCode刷題實戰(zhàn)24：兩兩交換鏈表中的節(jié)點
算法的重要性，我就不多說了吧，想去大廠，就必須要經(jīng)過基礎(chǔ)知識和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選 ！
今天和大家聊的問題叫做兩兩交換鏈表中的節(jié)點，我們先來看題面：
https://leetcode-cn.com/problems/swap-nodes-in-pairs/
Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes itself may be changed.
題意
樣例
給定 1->2->3->4, 你應(yīng)該返回2->1->4->3.
題解
從鏈表的頭節(jié)點 head 開始遞歸。
每次遞歸都負責交換一對節(jié)點。由 firstNode 和 secondNode 表示要交換的兩個節(jié)點。
下一次遞歸則是傳遞的是下一對需要交換的節(jié)點。若鏈表中還有節(jié)點，則繼續(xù)遞歸。
交換了兩個節(jié)點以后，返回 secondNode，因為它是交換后的新頭。
在所有節(jié)點交換完成以后，我們返回交換后的頭，實際上是原始鏈表的第二個節(jié)點。
class?Solution?{
????public?ListNode swapPairs(ListNode head) {
????????// If the list has no node or has only one node left.
????????if?((head == null) || (head.next == null)) {
????????????return?head;
????????}
????????// Nodes to be swapped
????????ListNode firstNode = head;
????????ListNode secondNode = head.next;
????????// Swapping
????????firstNode.next = swapPairs(secondNode.next);
????????secondNode.next = firstNode;
????????// Now the head is the second node
????????return?secondNode;
????}
}
上期推文：
評論
圖片
表情