1.就地反转法反转链表
就地反转法和头插法思想类似, 唯一的区别就是头插法创建一个新的链表来实现, 而就地反转法是直接修改原链表式实现反转
-
初始状态下, 令beg 指向第一个节点, end 指向beg.next, 如图
就地反转表的初始状态
2.将end所指的节点从链表上摘除, 然后再天机到当前链表的头部,如图
反转节点2
3.将end指向下一个节点,到此已经完成接下来重复上面的操作可完成剩余反转, 即将end所指向的节点3从链表摘除, 再添加到链表的头部
反转节点3
4.重复以上步骤
反转节点4
具体代码实现(swift)
func reverseList( head:inout ListNode?) -> ListNode? {
// 2个额外的指针, 分别指向节点1和节点2
var beg = head
var end = head?.next
// 循环链表
while end != nil {
// 假设 链表为1,2,3,4,5
// 将end从链表中移除, 此时链表head 为 1,3,4,5
beg?.next = end?.next
// 将head 移动到表头 2,1,3,4,5
end?.next = head
// head 指向新的链表, 2,1,3,4,5
head = end
// 移动end执行的指向, 即执行beg.next 节点, 为下次反转准备
end = beg?.next
}
return head
}
2.头插法
所谓头插法，是指在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转版。
1.创建空链表
创建空链表
2.从原链表中摘除头部节点 1，并以头部插入的方式将该节点添加到新链表中
放置节点1到新链表
3.从原链表中摘除头部节点 2，以头部插入的方式将该节点添加到新链表中
放置节点2到新链表
4.继续重复以上工作，先后将节点 3、4 从原链表中摘除，并以头部插入的方式添加到新链表中
继续放置其他节点
具体代码实现(swift)
func reverseList( head:inout ListNode?) -> ListNode? {
// 新链表
var pHead: ListNode? = nil
// 临时链表
var temp: ListNode? = nil
// 下一个
while head != nil {
temp = head
// 将temp 从head中摘除
head = head?.next
// temp 插入到new_head头部
temp?.next = pHead
pHead = temp
}
return pHead
}
2.应用, 寻找两个view共同父视图?
暴力破解, 复杂度 m*n
思考: view通过调用superview 能得到父视图, 其结构跟链表类似, 因此可以转化为寻找两个链表的公共节点问题
var temp1 = v1.superview
var temp2 = v2.superview
while temp1 != nil{
while(temp2 != nil){
if temp2 == temp1 {
print("父视图相同了")
}
temp2 = temp2?.superview
}
temp1 = temp1?.superview
}
寻找两个链表的公共节点, 算法复杂度为(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;
}
