鏈表這部分最常見(jiàn)的就是鏈表反轉(zhuǎn)婿崭，這里主要針對(duì)三種題型來(lái)對(duì)鏈表的反轉(zhuǎn)問(wèn)題進(jìn)行了講解。分別對(duì)應(yīng)leetcode中的題目如下：
反轉(zhuǎn)一個(gè)單鏈表
兩兩交換鏈表中的節(jié)點(diǎn)
每 k 個(gè)節(jié)點(diǎn)一組翻轉(zhuǎn)鏈表
每個(gè)問(wèn)題難度循序漸漸魏保，以下算法通過(guò)scala語(yǔ)言實(shí)現(xiàn)
- 首先定義數(shù)據(jù)結(jié)構(gòu)：
ListNode
class ListNode(var _x: Int = 0){
var next: ListNode = _
var x: Int = _x
}
數(shù)據(jù)結(jié)構(gòu)的定義決定了你的算法實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)也是一個(gè)很容易忽略的問(wèn)題。
反轉(zhuǎn)一個(gè)單鏈表
算法思路如下：因?yàn)橐獙⒐?jié)點(diǎn)的指針?lè)崔D(zhuǎn)柑贞，也就是當(dāng)前節(jié)點(diǎn)的
next指針由原來(lái)的指向后續(xù)節(jié)點(diǎn)變?yōu)橹赶蚯靶蚬?jié)點(diǎn)嫂伞，那么我們這里需要三個(gè)變量：cur孔厉、pre拯钻、next分別來(lái)指向當(dāng)前節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的前節(jié)點(diǎn)撰豺，當(dāng)前節(jié)點(diǎn)的后節(jié)點(diǎn)粪般。因?yàn)槲覀兒竺嬉淖?code>cur.next的值，為了防止原始指針丟失污桦，用next指針來(lái)保存亩歹，next = cur.next, 因?yàn)樾枰獙?code>cur.next指向前序節(jié)點(diǎn)，那么這里用pre保存前序節(jié)點(diǎn)的指針凡橱，然后另cur.next = pre就好了小作。
這里的指針只是變動(dòng)了一次，由后續(xù)節(jié)點(diǎn)變?yōu)榱饲靶蚬?jié)點(diǎn)稼钩。
具體實(shí)現(xiàn)如下：
def swapNodes(head: ListNode): ListNode = {
if(head == null){
return head
}
//pre does not need to initialize
var pre: ListNode = null
var cur = head
var next: ListNode = null
while(cur.next != null){
next = cur.next
cur.next = pre
pre = cur
cur = next
}
cur.next = pre
cur
}
兩兩交換鏈表中的節(jié)點(diǎn)
算法思路如下：跟簡(jiǎn)單的反轉(zhuǎn)鏈表相比顾稀，這里做了限定，只是兩兩節(jié)點(diǎn)的指針?lè)崔D(zhuǎn)。這里使用兩個(gè)變量分別保存需要反轉(zhuǎn)的節(jié)點(diǎn)的前序節(jié)點(diǎn)（
pre）和需要反轉(zhuǎn)的節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)（post）燕酷。然后當(dāng)pre.next != null && pre.next.next != null時(shí)進(jìn)行指針的變動(dòng)劫乱。變動(dòng)之后在更新pre和post在繼續(xù)變動(dòng)。
這里指針需要變動(dòng)三次：
pre.next.next.next = pre.next
pre.next = pre.next.next
pre.next.next.next = post
具體實(shí)現(xiàn)如下：
def swapInPairs(head: ListNode): ListNode = {
val dummy: ListNode = new ListNode(-1)
var pre = dummy
dummy.next = head
var post: ListNode = null
while (pre.next != null && pre.next.next != null){
post = pre.next.next.next
pre.next.next.next = pre.next
pre.next = pre.next.next
pre.next.next.next = post
pre = pre.next.next
}
dummy.next
}
因?yàn)閮蓛山粨Q的時(shí)候頭結(jié)點(diǎn)會(huì)改變诡宗，這里在頭節(jié)點(diǎn)前面加一個(gè)虛擬節(jié)點(diǎn)
dummy，讓dummy .next = head击儡，后面隨便的變換塔沃，我們只要保證后面dummy.next一直指向改變后的頭結(jié)點(diǎn)就好，最后返回dummy.next就好阳谍。這里pre = dummy蛀柴， pre.next = pre.next.next保證了dummy.next一直指向改變后的頭結(jié)點(diǎn)。
每 k 個(gè)節(jié)點(diǎn)一組翻轉(zhuǎn)鏈表
這里跟兩兩節(jié)點(diǎn)反轉(zhuǎn)的不同是由原來(lái)的2變成了k矫夯，因?yàn)閗不確定鸽疾，所以不能簡(jiǎn)單的通過(guò)一個(gè)循環(huán)來(lái)判斷并變換。
我們通過(guò)一個(gè)函數(shù)來(lái)交換需要交換的k個(gè)節(jié)點(diǎn)训貌，然后每次向后取k個(gè)節(jié)點(diǎn)將其傳入該函數(shù)進(jìn)行變換制肮，另一個(gè)函數(shù)來(lái)取k個(gè)節(jié)點(diǎn)。
交換函數(shù)需要傳入兩個(gè)指針递沪，一個(gè)是k個(gè)節(jié)點(diǎn)的前節(jié)點(diǎn)(pre)豺鼻，一個(gè)是k個(gè)節(jié)點(diǎn)的后節(jié)點(diǎn)(post),返回值是交換后的pre節(jié)點(diǎn)。
-1->1->2->3->4->5
| |
pre next
-1->3->2->1->4->5
| |
pre next
只要next走過(guò)k個(gè)節(jié)點(diǎn)款慨，就可以調(diào)用翻轉(zhuǎn)函數(shù)來(lái)進(jìn)行局部翻轉(zhuǎn)了
代碼實(shí)現(xiàn)如下：
def swapInKNodes(head: ListNode, k: Int): ListNode = {
if(head == null){
return head
}
var count: Int = 0
val dummy = new ListNode(-1)
dummy.next = head
var pre = dummy
var post: ListNode = head
while(post.next != null){
count = count + 1
post = post.next
if(count % k == 0){
pre = swapKNodes(pre, post)
println("pre: "+ pre.x)
}
}
dummy.next
}
def swapKNodes(pre: ListNode, post: ListNode): ListNode = {
val head = pre.next
var last = pre.next
var next : ListNode = null
var cur = last.next
while(cur != post){
next = cur.next
cur.next = last
last = cur
cur = next
}
head.next = post
pre.next = last
head
}
