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

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

程序员文章站 2022-06-30 19:37:44
反转一个单链表。 进阶:链表可以迭代或递归地反转。你能否两个都实现一遍? 示例 : 给定这个链表:1->2->3->4->5 返回结果: 5->4->3->2->1 题目链接 解题思路: 1. 迭代版本: 循环列表,定义两个指针,一个指针是已经迭代完的链表的最后一个节点称为last_node,一个指 ......

反转一个单链表。

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

示例 :

给定这个链表: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愿和各位一起进步!

微信公众号:

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