leetcode中如何解決兩兩交換鏈表中的節(jié)點問題

發(fā)布時間：2022-01-17 11:48:36 來源：億速云閱讀：171 作者：小新欄目：大數(shù)據(jù)

小編給大家分享一下leetcode中如何解決兩兩交換鏈表中的節(jié)點問題，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

題目鏈接

https://leetcode-cn.com/problems/swap-nodes-in-pairs/

題目描述

給定一個鏈表，兩兩交換其中相鄰的節(jié)點，并返回交換后的鏈表。

你不能只是單純的改變節(jié)點內(nèi)部的值，而是需要實際的進(jìn)行節(jié)點交換。

示例:

給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.

解題方案

思路

標(biāo)簽：鏈表
本題的遞歸和非遞歸解法其實原理類似，都是更新每兩個點的鏈表形態(tài)完成整個鏈表的調(diào)整
其中遞歸解法可以作為典型的遞歸解決思路進(jìn)行講解

遞歸寫法要觀察本級遞歸的解決過程，形成抽象模型，因為遞歸本質(zhì)就是不斷重復(fù)相同的事情^[1]。而不是去思考完整的調(diào)用棧，一級又一級，無從下手。如圖所示，我們應(yīng)該關(guān)注一級調(diào)用小單元的情況，也就是單個f(x)。

leetcode中如何解決兩兩交換鏈表中的節(jié)點問題 — 調(diào)用棧

其中我們應(yīng)該關(guān)心的主要有三點：

返回值
調(diào)用單元做了什么
終止條件

在本題中：

返回值：交換完成的子鏈表
調(diào)用單元：設(shè)需要交換的兩個點為head和next，head連接后面交換完成的子鏈表，next連接head，完成交換
終止條件：head為空指針或者next為空指針，也就是當(dāng)前無節(jié)點或者只有一個節(jié)點，無法進(jìn)行交換

代碼

遞歸解法

class Solution {    public ListNode swapPairs(ListNode head) {        if(head == null || head.next == null){            return head;        }        ListNode next = head.next;        head.next = swapPairs(next.next);        next.next = head;        return next;    }}

非遞歸解法

class Solution {    public ListNode swapPairs(ListNode head) {        ListNode pre = new ListNode(0);        pre.next = head;        ListNode temp = pre;        while(temp.next != null && temp.next.next != null) {            ListNode start = temp.next;            ListNode end = temp.next.next;            temp.next = end;            start.next = end.next;            end.next = start;            temp = start;        }        return pre.next;    }}