1.就地反轉(zhuǎn)法反轉(zhuǎn)鏈表
就地反轉(zhuǎn)法和頭插法思想類似, 唯一的區(qū)別就是頭插法創(chuàng)建一個(gè)新的鏈表來實(shí)現(xiàn), 而就地反轉(zhuǎn)法是直接修改原鏈表式實(shí)現(xiàn)反轉(zhuǎn)
-
初始狀態(tài)下, 令beg 指向第一個(gè)節(jié)點(diǎn), end 指向beg.next, 如圖
就地反轉(zhuǎn)表的初始狀態(tài)
2.將end所指的節(jié)點(diǎn)從鏈表上摘除, 然后再天機(jī)到當(dāng)前鏈表的頭部,如圖
反轉(zhuǎn)節(jié)點(diǎn)2
3.將end指向下一個(gè)節(jié)點(diǎn),到此已經(jīng)完成接下來重復(fù)上面的操作可完成剩余反轉(zhuǎn), 即將end所指向的節(jié)點(diǎn)3從鏈表摘除, 再添加到鏈表的頭部
反轉(zhuǎn)節(jié)點(diǎn)3
4.重復(fù)以上步驟
反轉(zhuǎn)節(jié)點(diǎn)4
具體代碼實(shí)現(xiàn)(swift)
func reverseList( head:inout ListNode?) -> ListNode? {
// 2個(gè)額外的指針, 分別指向節(jié)點(diǎn)1和節(jié)點(diǎn)2
var beg = head
var end = head?.next
// 循環(huán)鏈表
while end != nil {
// 假設(shè) 鏈表為1,2,3,4,5
// 將end從鏈表中移除, 此時(shí)鏈表head 為 1,3,4,5
beg?.next = end?.next
// 將head 移動(dòng)到表頭 2,1,3,4,5
end?.next = head
// head 指向新的鏈表, 2,1,3,4,5
head = end
// 移動(dòng)end執(zhí)行的指向, 即執(zhí)行beg.next 節(jié)點(diǎn), 為下次反轉(zhuǎn)準(zhǔn)備
end = beg?.next
}
return head
}
2.頭插法
所謂頭插法，是指在原有鏈表的基礎(chǔ)上舌狗，依次將位于鏈表頭部的節(jié)點(diǎn)摘下朝氓，然后采用從頭部插入的方式生成一個(gè)新鏈表赵哲，則此鏈表即為原鏈表的反轉(zhuǎn)版。
1.創(chuàng)建空鏈表
2.從原鏈表中摘除頭部節(jié)點(diǎn) 1，并以頭部插入的方式將該節(jié)點(diǎn)添加到新鏈表中
3.從原鏈表中摘除頭部節(jié)點(diǎn) 2华嘹，以頭部插入的方式將該節(jié)點(diǎn)添加到新鏈表中
4.繼續(xù)重復(fù)以上工作，先后將節(jié)點(diǎn) 3俯渤、4 從原鏈表中摘除侦鹏，并以頭部插入的方式添加到新鏈表中
具體代碼實(shí)現(xiàn)(swift)
func reverseList( head:inout ListNode?) -> ListNode? {
// 新鏈表
var pHead: ListNode? = nil
// 臨時(shí)鏈表
var temp: ListNode? = nil
// 下一個(gè)
while head != nil {
temp = head
// 將temp 從head中摘除
head = head?.next
// temp 插入到new_head頭部
temp?.next = pHead
pHead = temp
}
return pHead
}
2.應(yīng)用, 尋找兩個(gè)view共同父視圖?
暴力破解, 復(fù)雜度 m*n
思考: view通過調(diào)用superview 能得到父視圖, 其結(jié)構(gòu)跟鏈表類似, 因此可以轉(zhuǎn)化為尋找兩個(gè)鏈表的公共節(jié)點(diǎn)問題
var temp1 = v1.superview
var temp2 = v2.superview
while temp1 != nil{
while(temp2 != nil){
if temp2 == temp1 {
print("父視圖相同了")
}
temp2 = temp2?.superview
}
temp1 = temp1?.superview
}
尋找兩個(gè)鏈表的公共節(jié)點(diǎn), 算法復(fù)雜度為(m+n)
func FindFirstCommonNode(pHead1: ListNode?, pHead2: ListNode?)-> ListNode?
{
var p: ListNode? = pHead1;
var q: ListNode? = pHead2;
while(p != q){
p = (p != nil) ? p?.next : pHead2;
q = (q != nil) ? q?.next : pHead1;
print("p:\(p?.val) q: \(q?.val)")
}
return p;
}
