精华内容
下载资源
问答
  • bat面试题 python 单链表反转排序

    千次阅读 2017-09-27 19:50:21
    bat面试题 python 单链表反转排序

    单链表反转python实现

    单链表的反转可以使用循环,也可以使用递归的方式

    1.循环反转单链表

    循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可。

        

    代码:

    [python] view plain copy
    1. class ListNode:  
    2.     def __init__(self,x):  
    3.         self.val=x;  
    4.         self.next=None;  
    5.   
    6. def nonrecurse(head):              #循环的方法反转链表  
    7.     if head is None or head.next is None:  
    8.         return head  
    9.     pre=None  
    10.     cur=head
    11.     while cur:  
    12.         h=cur  
    13.         tmp=cur.next 
    14.         cur.next=pre  
    15.         pre=cur  
    16.         cur=tmp
    17.     return h 
    18.       
    19. head=ListNode(1)    #测试代码  
    20. p1=ListNode(2)      #建立链表1->2->3->4->None;  
    21. p2=ListNode(3)  
    22. p3=ListNode(4)  
    23. head.next=p1 
    24. p1.next=p2  
    25. p2.next=p3  
    26. p=nonrecurse(head);   #输出链表 4->3->2->1->None  
    27. while p:  
    28.     print(p.val)
    29.     p=p.next  

    2.递归实现单链表反转

    [python] view plain copy
    1. class ListNode:  
    2.     def __init__(self,x):  
    3.         self.val=x;  
    4.         self.next=None;  
    5.   
    6.       
    7. def recurse(head,newhead):    #递归,head为原链表的头结点,newhead为反转后链表的头结点  
    8.     if head is None:  
    9.         return ;  
    10.     if head.next is None:  
    11.         newhead=head;  
    12.     else :  
    13.         newhead=recurse(head.next,newhead);  
    14.         head.next.next=head;  
    15.         head.next=None;  
    16.     return newhead;  
    17.       
    18. head=ListNode(1);               #测试代码  
    19. p1=ListNode(2);                 # 建立链表1->2->3->4->None  
    20. p2=ListNode(3);  
    21. p3=ListNode(4);  
    22. head.next=p1;  
    23. p1.next=p2;  
    24. p2.next=p3;  
    25. newhead=None;  
    26. p=recurse(head,newhead);           #输出链表4->3->2->1->None  
    27. while p:  
    28.     print p.val;  
    29.     p=p.next;  

    单链表排序

    class listNode:
        def __init__(self,x):
            self.val = x
            self.next  = None
        def createList(self,a):
            if a is None:
               print('no elements')
               return
            head=listNode(a[0])
            p=head
            i=1
            n=len(a)
            while i<n:
                t=listNode(a[i])
                p.next=t
                p=t
                i=i+1
            return head
        def scanList(self,head):
           if head is None:
              print("no elements")
              return
           print(head.val)
           while head.next:
                 print(head.next.val)
                 head=head.next
        def sortList(self, head):
            if head is None or head.next is None:
                return head
            mid = (head.val + head.next.val) / 2
            if head.val > head.next.val:
                lhead, rhead = head.next, head
            else:
                lhead, rhead = head, head.next
            lit, rit = lhead, rhead
            it = head.next.next
            while it is not None:
                if it.val > mid:
                    rit.next = it
                    rit = it
                else:
                    lit.next = it
                    lit = it
                it = it.next
            lit.next, rit.next = None, None
            lhead = self.sortList(lhead)
            rhead = self.sortList(rhead)
            it = lhead
            while it.next is not None:
                it = it.next
            it.next = rhead
            return lhead
    
    l=listNode(0)
    a=[2,5,9,3,6,1,0,7,4,19]
    head=l.createList(a)
    l.scanList(head)
    newhead=l.sortList(head)
    print('sorted list:')
    l.scanList(newhead)

    展开全文
  • python单链表反转

    2021-02-25 06:56:54
    def reverseList(head): if head is None or head.next is None: return head pre_node = head current_node = head while current_node is not None: next_node = current_node.next # 暂存当前节点的next...
    def reverseList(head):
    	if head is None or head.next is None:
    		return head
    	pre_node = head
    	current_node = head
    	while current_node is not None:
    		next_node = current_node.next  # 暂存当前节点的next节点
    		current_node.next = pre_node   # 当前节点的next指向初始化的节点
    		pre_node = current_node        # 初始化的节点为当前节点
    		current_node = next_node       # 当前节点为暂存的节点
    	return pre_node
    
    展开全文
  • python实现单链表反转

    2020-10-10 10:37:46
    class Link: def __init__(self): self.n = 0 self.fist_node = Node() super(Link, self).__init__() def isEmply(self): return self.n == 0 def clear(self): self.n = 0 self.fist_node = Node() ...
    class Link:
    
        def __init__(self):
            self.n = 0
            self.fist_node = Node()
            super(Link, self).__init__()
    
        def isEmply(self):
            return self.n == 0
    
        def clear(self):
            self.n = 0
            self.fist_node = Node()
    
        def add(self, node):
            item = self.fist_node
            while item.next_addr:
                item = item.next_addr
            item.next_addr = node
            self.n += 1
    
        def addx(self, i, node):
            if i > self.n:
                return -1
            temp = self.fist_node
            for x in range(1, self.n + 1):
                if x == i:
                    break
                temp = temp.next_addr
    
            node.next_addr = temp.next_addr
            temp.next_addr = node
    
        def get(self, i):
            if self.n == 0:
                return -1
            temp = self.fist_node.next_addr
            for x in range(1, self.n + 1):
                if x == i:
                    break
                temp = temp.next_addr
            return temp.value
    
        def delete(self, i):
            if i > self.n or i <= 0:
                return -1
            temp = self.fist_node
            for x in range(1, self.n + 1):
                if x == i:
                    break
                temp = temp.next_addr
            temp.next_addr = temp.next_addr.next_addr
            self.n -= 1
    
        def reverse(self):
            Link.node_reverse(self, self.fist_node.next_addr)
    
        def node_reverse(self, node):
            if node.next_addr:
                item = Link.node_reverse(self, node.next_addr)
                item.next_addr = node
                node.next_addr = None
                return node
    
            else:
                self.fist_node.next_addr = node
                return node
    
    
    class Node:
        def __init__(self, pre=None, value=None, next_addr=None):
            self._pre = pre
            self._value = value
            self._next_addr = next_addr
    
        @property
        def pre(self):
            return self._pre
    
        @pre.setter
        def pre(self, addr):
            self._pre = addr
    
        @property
        def next_addr(self):
            return self._next_addr
    
        @next_addr.setter
        def next_addr(self, addr):
            self._next_addr = addr
    
        @property
        def value(self):
            return self._value
    
        @value.setter
        def value(self, value):
            self._value = value
    
    
    if __name__ == '__main__':
    
        link = Link()
        node = Node(value='11')
        node1 = Node(value='12')
        node2 = Node(value='13')
        node3 = Node(value='13')
    
        link.add(node)
        link.add(node1)
        link.add(node2)
        link.add(node3)
    
        print(link.get(1))
        print(link.get(2))
        print(link.get(3))
        print(link.get(4))
    
        link.reverse()
        print(link.get(1))
        print(link.get(2))
        print(link.get(3))
        print(link.get(4))
    
    
    
    展开全文
  • 单链表反转python实现,简洁详细易于理解,附带注释易于分析
  • python实现单链表反转(经典笔试题)

    万次阅读 多人点赞 2018-07-16 22:40:18
    0、说在前面的话  链表结构,说难不难,说易不易,一定要亲自编程实现一下。其次就是一定要耐心,慢慢... 建立三个变量,L、M、R互相赋值迭代,并建立指向关系,从而实现单链表反转。 3、python代码实现 cla...

    0、说在前面的话

         链表结构,说难不难,说易不易,一定要亲自编程实现一下。其次就是一定要耐心,慢慢去体会其中的道道,博主一开始也是有点懵逼的,后来仔细琢磨了一下终于搞明白了,相信聪明的你也一定可以,有问题可以留言交流。

    1、单链表结构

    2、反转的想法

          建立三个变量,L、M、R互相赋值迭代,并建立指向关系,从而实现单链表的反转。

    3、python代码实现

    class Node(object):
        def __init__(self, data, next=None):
            self.val = data
            self.next = next
    
    def fun4(head):
        if head == None:
            return None
        L,M,R = None,None,head
        while R.next != None:
            L = M
            M = R
            R = R.next
            M.next = L
        R.next = M
        return R
    #测试用例
    if __name__ == '__main__':
        l1 = Node(3)
        l1.next = Node(2)
        l1.next.next = Node(1)
        l1.next.next.next = Node(9)
        l = fun4(l1)
        print (l.val, l.next.val, l.next.next.val, l.next.next.next.val)

     

    展开全文
  • 主要介绍了单链表反转python实现,分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下
  • 三个指针实现单链表反序输出 class Node(object): def __init__(self, item, next=None): self.val = item self.next = next #三个指针遍历反转 def reverse(head): #p、q指针指定先后两个节点 if head == ...
  • 反转1_头插4. 反转2 1. 链表节点类 class LinkListNode(object): def __init__(self, val, next=None): self.val = val self.next = next 2. 创建链表(附赠) def CreateLinkList(l): """ l: list, 节点值...
  • 链表是一种基础的数据结构,也是算法学习的重中之重。其中单链表反转是一个经常会被考察到的知识点。...现在来给大家简单介绍一下单链表反转算法实现的基本原理和python代码实现。 算法基本原理及python...
  • 单链表反转python实现

    千次阅读 2016-08-28 19:16:00
    单链表反转可以使用循环,也可以使用递归的方式 1.循环反转单链表 循环的方法中,使用pre指向前一个结点,cur指向当前结点,每次把cur->next指向pre即可。   代码: [python] view
  • 单链表反转-python实现

    2019-02-12 22:32:02
    单链表反转,可以使用 循环、递归 两种方式 循环方式 class ListNode: def __init__(self, x): self.val = x self.next = None def non_recurse(head): if head is None or head.next is None: return ...
  • 单链表反转 | 不合法的路径地址转变为...1. python单链表反转 单链表结构 单链表反转问题就不细说,网上能找到很多。使用三个变量L、M、R互相赋值迭代,并建立指向关系,从而实现单链表的反转。直接上代码 cl...
  • 单链表反转_python

    万次阅读 多人点赞 2019-03-21 13:01:10
    反转单链表反转过程如下: 第一步:next = head.next 将 head.next 赋值给 next 变量,即next 指向了节点2,先将节点2 保存起来。 第二步:head.next = pre (初始pre==None) 将 pre 变量赋值给 ...
  • 单链表反转Python

    2019-06-24 18:21:50
    最近一直在学数据结构的知识,今天接触到了链表,通过Python实现了单链表,双向链表以及单向循环链表。采用面向对象的思想,对其进行封装成一个类,就类似list的一样,具有一些简单的操作函数,如:append、insert...
  • 单链表反转

    2019-02-28 23:19:00
    /usr/bin/python#递归实现单链表反转 class ListNode(object): def __init__(self,x): self.val=x self.next=None def recurse(head,newhead): #递归,head为原链表的头结点,newhead为反转后链表的头结点 if head ...
  • 单链表反转 单链表反转这道题可谓是链表里面的高频问题了,差不多可以说只要被问到链表,就会问单链表反转。 今天我们就一起来看下。 题目链接: https://leetcode-cn.com/problems/reverse-linked-list/ 题目描述:...
  • 链表是一种基础的数据结构,也是算法学习的重中之重。其中单链表反转是一个经常会被考察到的知识点。...现在来给大家简单介绍一下单链表反转算法实现的基本原理和python代码实现。  算法基本原理及python代码 1...

空空如也

空空如也

1 2 3 4 5 ... 15
收藏数 285
精华内容 114
关键字:

python单链表反转

python 订阅