欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指offer(python)-题目15-反转链表******

程序员文章站 2022-06-17 18:10:14
...

题目描述
输入一个链表,反转链表后,输出新链表的表头。
链表是通过一个个节点组成的,每个节点都包含了称为cargo的基本单元,它也是一种递归的数据结构。它能保持数据之间的逻辑顺序,但存储空间不必按照顺序存储。
如图:

剑指offer(python)-题目15-反转链表******

链表的基本元素有:

节点:每个节点有两个部分,左边部分称为值域,用来存放用户数据;右边部分称为指针域,用来存放指向下一个元素的指针。
head:head节点永远指向第一个节点 tail: tail永远指向最后一个节点 None:链表中最后一个节点的指针域为None值

思路1:
因为链表是有head和tail,而他们是有一个方向的,因此我们想直接进行类似list[::-1]这种反转就不是太方便。在下面的算法中,我们通过将链表截断,而后再拼接的方式进行反转。

以{1,2,3}链表作为例子,来说明下面算法中while迭代的流程(手工debug…)

1.将{2,3}的地址指向给tmp
2.将last=None指向pHead.next,这个时候pHead链表就被截断了,pHead只剩下了1,因为他的下一步指向了None
3.将此时的pHead,也就是1指向给last,这时候last为{1}
4.将tmp={2,3}指向给pHead,此时这轮迭代结束,开启下一轮. 这时,pHead是{2,3},last是{1}

5.将{3}指向给tmp
6.将{1}指向给pHead.next,也就是2的下一步值,因此这时候pHead就变成了{2,1}
7.将{2,1}指向给last
8.将{3}指向给pHead,此时这轮迭代结束,开启下一轮. 这时,pHead是{3},last是{2,1}

9.将None指向了tmp
10.将{2,1}指向给pHead.next,也就是{3}的下一步值,这个时候pHead就变成了{3,2,1}
11.将{3,2,1}指向给last
12.将None指向给pHead,此时这轮迭代结束,while迭代结束。 这时pHead是{None},last是{3,2,1}
https://www.jianshu.com/p/e385d9c06672
根据下图,先给定一个空的链表newList,然后判断传入的链表head是不是空链表或者链表元素只有一个,如果是,直接返回就可以。如果不是,则对链表进行迭代,然后给一个临时变量temp存储head.next,然后改变head.next的指向newList,然后把head赋值给newList,接着让head等于临时变量temp,就这样一直迭代完整个链表,返回newList就可以
剑指offer(python)-题目15-反转链表******

class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        if not pHead or not pHead.next:
            return pHead
        last =None
        while pHead:
            tmp = pHead.next#将下一步的地址指向给tmp
            pHead.next=last#将一个新的链表指向给旧链表pHead,这个时候就把pHead截断了,只剩下前面的链表值
            last=pHead#将旧链表的地址指向给新链表
            pHead=tmp#将旧链表原来的下一步只指向给pHead
        return last


思路2:–递归

思路:假设链表为[1,2,3,4,5]先迭代到链表末尾5,然后从5开始依次反转整个链表
如下图所示,先迭代待最后一位5,并且设置一个新的节点newList作为反转后链表的头结点,由于整个链表反转后的头就是最后一个数,所以newList存放的一直是反转后的头结点的地址,将head指向的地址赋值给head->next->next指针,并且一定要记得让head->next
=NULL,也就是断开现在指针的链接,否则新的链表形成了环,下一层head->next->next赋值的时候会覆盖后续的值。依次反转。
剑指offer(python)-题目15-反转链表******

class Solution:
    # 返回ListNode
    def ReverseList(self, head):
        if head==None or head.next==None:
            return head
        newlist=ReverseList(head.next)
        head.next.next=head
        head.next=None
        return newlist