数据结构与算法 —— 链表linked list(05)

2018-06-18 02:34:02来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

反转一个单链表。

进阶:
链表可以迭代或递归地反转。你能否两个都实现一遍?

示例 :

给定这个链表:1->2->3->4->5

返回结果: 5->4->3->2->1

题目链接

解题思路:

1. 迭代版本:

循环列表,定义两个指针,一个指针是已经迭代完的链表的最后一个节点称为last_node,一个指针是已经迭代完的节点的第一个节点称为next_node。

刚开始的时候last_node 和next_node都指向链表head,循环last_node的next节点定义为cur,把last_node的next指向cur的next指针,把cur的next指向next_node节点。

next_node赋值为当前的cur节点。

最后返回next_node即可。

图如下

1   ->2    ->3   ->4   ->5

|

next_node

last_node

循环完1之后

2   ->1    ->3   ->4   ->5

|    |

|      last_node

next_node

代码如下:

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return None
        last_node = head
        next_node = head
        while (last_node.next):
            cur = last_node.next
            cur_next = cur.next
            cur.next = next_node
            last_node.next = cur_next
            next_node = cur
        return next_node

2. 递归版本

递归:递归,就是在运行的过程中调用自己。

构成递归需具备的条件:
1. 子问题须与原始问题为同样的事,且更为简单;
2. 不能无限制地调用本身,须有个出口,化简为非递归状况处理
先将从第一个点开始翻转转换成从下一个节点开始翻转 ,直至只剩一个节点 。
代码如下:
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if  head is None or head.next is None:
            return head
        pre_node = self.reverseList(head.next)
        head.next.next=head
        head.next=None

        return pre_node

 

反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:
1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

解题思路:

 可以先找到翻转的开始位置,这里是2,然后根据这个位置将链表断开:1->null, 2->3->4->5->null,这就形成了两个链表。

然后,将第二个链表依次取头结点,放在1的后面:

1. 1->2->null, 3->4->5->null

2. 1->3->2->null, 4->5->null

。。。

这样的循环进行几次呢,循环3次,也就是n - m + 1次

之后再将现在的两个链表合并即可。代码就可以得到了

代码如下:

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)  
        dummy.next = head  
        pre = dummy  
        num = 1  
        # 找到要翻转部分的开始  
        while num != m:  
            pre = pre.next  
            num += 1  
        # gap为循环的次数  
        gap = n - m + 1  
        # 第二部分  
        next_part = pre.next  
        # 设置第一部分的尾节点,目的在于最后的合并  
        tail = next_part  
        pre.next = None  
        while gap != 0:  
            cur = next_part  
            next_part = next_part.next  
            temp = pre.next  
            pre.next = cur  
            cur.next = temp  
            gap -= 1  
        # 两部分合并  
        tail.next = next_part  
        return dummy.next    

  

 

coding交流群:226704167,,郑州程序员群:59236263愿和各位一起进步!

微信公众号:

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:python2.7练习小例子(三)

下一篇:铁乐学python26_hashlib+configparser+logging模块