单链表反转

1.就地反转法反转链表

就地反转法和头插法思想类似, 唯一的区别就是头插法创建一个新的链表来实现, 而就地反转法是直接修改原链表式实现反转

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，并以头部插入的方式将该节点添加到新链表中

3.从原链表中摘除头部节点 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;
    }

原文地址