多种解法破解链表

多种解法破解链表

0.说在前面1.旋转链表2.相交链表3.作者的话

0.说在前面

我们算法已经到了leetcode攀登之旅(21)!本周还差一次刷题推送,这篇就是,没错,让各位久等了,这次放的可是多种解法干货!!!

这次刷的题为旋转链表与相交链表!!! 说明一下,下面有个图文是我跟范大大组织的一次算法训练周计划!有想法的可以留言哈!

1.旋转链表

题目

给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

思路

对于这个题目我想出了两种解法,现在分享一下。

解法一,让我想起了递归,然后未提交之前分析了一下复杂度,自己都觉得通过不了,你们懂的,递归效率不高!但是思路需要学会!

解法二,于是我开始想解法二,便发现了这道题的猫腻,那就是右移旋转k位置,如果是链表整数倍,那么旋转后链表不变,而如果不是链表整数倍,那么我们算出他的余数(k除以链表长度),真正移动的就是这个余数

那么下面一起来实战吧!

实现

递归实现

这个算法,仅供研读学习思路,通不过的哈,超时。。。递归算法效率本身就不高!

class Solution(object):
    def rotateRight(self, head, k):
        if k == 0 or head is None or head.next is None:
            return head
        for i in range(k):
            head = self.rightShift(head)
        return head
    def rightShift(self, head):
        pre = head
        curr = head.next
        while curr:
            if curr.next is None:
                curr.next = head
                pre.next = None
                return curr
            pre = pre.next
            curr = curr.next
        return curr

获取真正k实现

这个算法的关键在于,获取真正的右移次数,可以有效的解决时间复杂度问题!所以这里我将我的这个算法命名为获取真正k实现!

算法思路实现步骤:

  • 特殊情况处理

k为0,链表为空或者只有一个结点旋转后,还是本身,所以直接返回!

  • 非特殊情况处理

(1)循环链表一次,获取链表长度!

pre代表右旋转后的链表的最后一个结点,curr代表右旋转的后面链表前置的头结点!

这里举个实际例子,如图所示:

class Solution(object):
    def rotateRight(self, head, k):
        if k==0 or head is None or head.next is None:
            return head
        p=head
        size=0
        while p:
            size+=1
            p=p.next
        # 所循环的真实k
        # 真实k为原始k除以链表长度取模
        k=k%size
        p=head
        pre=head
        curr=head.next
        '''
        (1)真实k如果不为0,参照算法图
        (2)真实k如果为0,也就是原始k能够整除链表长度,
        那么此时的节点旋转后还是原链表,直接返回原链表
        '''
        if k:
            for i in range(size-k):
                pre=p
                curr=p.next
                p=p.next
            # 右旋转后的链表的最后一个结点next指向空
            pre.next=None
            # 保存最终链表的头节点
            newhead=curr
            # 循环后面移动到前面链表的所有结点,直到最后
            while curr.next:
                curr=curr.next
            # 让上述尾部结点连接原先的头节点,构成一个完整链表
            curr.next=head
            return newhead
        return head

算法分析

递归实现的时间复杂度为O(k*n),空间复杂度为O(n)

获取真实k实现的时间复杂度为O(n),空间复杂度为O(n)

2.相交链表

题目

编写一个程序,找到两个单链表相交的起始节点。

例如,下面的两个链表

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

在节点 c1 开始相交。

注意:

  • 如果两个链表没有交点,返回 null.
  • 在返回结果后,两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。

思路

对于这道题,也就是我今天想说的重点,这里给出哈希表,栈,以及双指针等多种解法!

算法思路直接写在代码实现处!

哈希表实现

直接定义一个字典,通过遍历链表A,并将A的所有结点添加到字典当中,循环遍历链表B,在字典中查找链表B的当前结点,如果存在,返回即可,否则为空!

def getIntersectionNode(self, headA, headB):
        dictA={}
        while headA:
            dictA[headA]=0
            headA=headA.next
        while headB:
            if headB in dictA:
                return headB
            headB=headB.next
        return None

这里定义两个list用来各自存放对应链表的结点,将链表A中结点入栈1,结点B中结点入栈2,我们知道只要两个链表相交,那么从相交点开始到后面的所有结点都一样!这里就通过弹出相同的结点,每次弹出的时候保存一下,直到找到两个链表的结点不同为止,此时返回刚才保存的结点,就是第一个相交的结点!

实现步骤:

首先特殊情况处理,然后结点各自入栈!首先需要判断一下最后结点相同不,如果不相同,直接不相交,返回None即可,否则需要对栈A与B出栈,并判断元素相同不!

    def getIntersectionNode(self, headA, headB):
        if headA is None or headB is None:
            return None
        stackA=[]
        stackB=[]
        while headA or headB:
            if headA:
                stackA.append(headA)
                headA=headA.next
            elif headB:
                stackB.append(headB)
                headB=headB.next
        if stackA[-1]!=stackB[-1]:
            return None
        while stackA and stackB:
            res=stackA[-1]
            stackA.pop()
            stackB.pop()
            # 防止A与B栈空
            if stackA and stackB:
                if stackA[-1].val!=stackB[-1].val:
                    return res
            else:
                return res
        return None

双指针计算size法

两个链表长度由于不一样,所以先通过循环找到各自链表的长度,然后让长链表的指针先走两个链表长度的差值,保证两个链表遍历长度一致!此时,让两个链表去比较,如果此时两个链表有相同结点,则相交,返回其中一个结点即可,否则返回None!

def getIntersectionNode(self, headA, headB):
    if headA is None or headB is None:
        return None
    size_A = 0
    size_B = 0
    pA = headA
    pB = headB
    while pA or pB:
        if pA:
            size_A += 1
            pA = pA.next
        elif pB:
            size_B += 1
            pB = pB.next
    if size_A > size_B:
        inter = size_A - size_B
        for i in range(inter):
            headA = headA.next
    elif size_A < size_B:
        inter = size_B - size_A
        for i in range(inter):
            headB = headB.next
    return self.search_Node(headA, headB)

def search_Node(self, headA, headB):
    while headA:
        if headA.val == headB.val:
            return headA
        headA = headA.next
        headB = headB.next
    return None

双指针不计算size法

对于这个实现,网上有个更牛逼的,直接几行代码写完,我们一起来拜读一下:

def getIntersectionNode(self, headA, headB):
    p1 = headA
    p2 = headB
    while(p1 != p2):
        p1 = headB if p1 == None else p1.next
        p2 = headA if p2 == None else p2.next
    return p1

双指针判断有无环状法

这里思路是将链表A先遍历到结尾,然后尾部连接头部,行成一个环,那么这道题就变成一个链表中是否有环问题。然后让链表B的头结点去访问即可!这里通过快慢指针来进行,对于这一块,之前写个证明,大家可以翻一下之前文章!

def getIntersectionNode(self, headA, headB):
    if headA is None or headB is None:
        return None
    pA=headA
    while pA.next:
        pA=pA.next
    pA.next=headA
    return self.detectCycle(headB)
def detectCycle(self, head):
    if not head:
        return None
    slow = fast = head
    while(slow and fast): 
        slow, fast =slow.next, fast.next
        if fast:
            fast = fast.next
            if slow is fast:  
                while(slow is not head):
                    slow, head = slow.next, head.next
                return head
    return None

但是可惜这个方法通不过,他不允许修改链表结构,哈哈,天真了~~

原文发布于微信公众号 - 光城(guangcity)

原文发表时间:2018-11-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券