一绍申、題目
給定一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)顾彰，并返回交換后的鏈表极阅。
示例:
給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.
說(shuō)明:
你的算法只能使用常數(shù)的額外空間。
你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值涨享，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換筋搏。
二、解題
創(chuàng)建四個(gè)指針left厕隧、first奔脐、second、right吁讨。
第一次：left = nil; first = 1; second = 2; right = 3.交換first和second帖族。left.next = second; second.next = first; first.next = right。
第二次：left = 1; first = 3; second = 4; right = nil. 交換first和second挡爵。....
使用while循環(huán)下去，知道second == nil甚垦，因?yàn)楫?dāng)second為nil時(shí)茶鹃，說(shuō)明最后只剩下一個(gè)或者零個(gè)涣雕，不需要在繼續(xù)轉(zhuǎn)換，返回第一個(gè)節(jié)點(diǎn)node即可闭翩。
時(shí)間復(fù)雜度：O(n).
三挣郭、代碼實(shí)現(xiàn)
class Solution {
func swapPairs(_ head: ListNode?) -> ListNode? {
var left: ListNode? = nil
var first = head
var second = first?.next
var right = second?.next
let node: ListNode? = second == nil ? head : second
while second != nil {
left?.next = second
second?.next = first
first?.next = right
left = first
first = right
second = first?.next
right = second?.next
}
return node
}
}
Demo地址：github
