单链表逆置

作者: GHope | 来源:发表于2018-11-17 21:56 被阅读10次

单链表逆置的思路

a:将单链表储存为数组,然后按照数组的索引逆序进行反转。
b:使用3个指针遍历单链表,逐个链接点进行反转。
c:从第2个节点到第N个节点,依次逐节点插入到第1个节点(head节点)之后,最后将第一个节点挪到新表的表尾。
d: 递归(相信我们都熟悉的一点是,对于树的大部分问题,基本可以考虑用递归来解决。但是我们不太熟悉的一点是,对于单链表的一些问题,也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树,因此可以考虑用递归来解决。或者说,因为单链表本身的结构也有自相似的特点,所以可以考虑用递归来解决)

具体实现

pre指向前一个结点,cur指向当前结点,next指向下一个节点。

循环实现

class Node(object):
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next


# 使用for循环并不能生成链表
# for i in range(1,10):
#     link = Node(i)
link = Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9)))))))))


def rev(link):
    pre = link
    cur = link.next
    pre.next = None
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    return pre


root = rev(link)
while root:
    print(root.data)
    root = root.next

递归实现

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


# 递归,head为原链表的头结点,newhead为反转后链表的头结点
def recurse(head, newhead):
    if head is None:
        return
    if head.next is None:
        newhead = head
    else:
        newhead = recurse(head.next, newhead)
        head.next.next = head
        head.next = None
    return newhead


# 建立链表1->2->3->4->None
head = ListNode(1)
p1 = ListNode(2)
p2 = ListNode(3)
p3 = ListNode(4)
head.next = p1
p1.next = p2
p2.next = p3
newhead = None

# 输出链表4->3->2->1->None
p = recurse(head, newhead)
while p:
    print(p.val)
    p = p.next

思路参考

相关文章

  • 算法面试:链表转置

    //单链表定义 普通的循环的方法。 //单链表逆置实现 递归调用方法

  • 插入任意数据形成有序单链表并逆置单链表

    可直接运行的完整C语言版有序单链表的生成和逆置标签:数据结构、线性表、带头结点的单链表、逆置单链表欢迎与喜欢数据结...

  • 单链表翻转

    单链表的就地逆置:就地逆置即空间复杂度为O(1)一:用数组存储单链表的值,然后重新逆序赋值,效率较低。二:利用三个...

  • 单链表逆置

    单链表逆置的思路 a:将单链表储存为数组,然后按照数组的索引逆序进行反转。b:使用3个指针遍历单链表,逐个链接点进...

  • 线性表之单链表实现

    线性表之单链表实现 实现单链表的初始化、插入、删除等基本运算 实现单链表的输入、输出运算 实现单链表的逆置、归并、...

  • 单链表的逆置

    方法一:迭代逆置 在上一篇文章的基础上添加Reverse()方法。 方法二:递归逆置

  • 王道数据结构练习

    练习2.5 //试编写算法将带头结点的单链表就地逆置#include #include #include u...

  • 单链表逆置算法详解

    思路: 首先创建一个单链表,返回一个头节点的指针( head 该头节点不为 NULL,其次进行单链表的逆置设置。具...

  • 链表逆置C语言完整代码

    链表逆置C语言完整代码

  • 单链表就地转置

    试写一道算法,实现单链表的就地逆置(反转),即利用原表的存储空间将线性表(a1,a2,⋯an)逆置(反转)为(an...

网友评论

本文标题:单链表逆置

本文链接:https://www.haomeiwen.com/subject/epalfqtx.html