反转链表

如果不在牛客网或者leetcode上运行代码 则要自己定义数据结构 如下:

 

定义如下:

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


class NodeHandle(object):
    def __init__(self):
        self.cur_node = None

    # 查找
    def find(self, node, num, a=0):
        while node:
            if a == num:
                return node
            a += 1
            node = node.next

    # 增加
    def add(self, data):
        node = Node()  # 实例化node
        node.val = data  # 赋值val
        node.next = self.cur_node  # 赋值next
        self.cur_node = node  # 存放上一个节点
        return node

    # 打印
    def printNode(self, node):
        while node:
            print('node: ', node, ' value: ', node.val, ' next: ', node.next)
            node = node.next

    # 删除
    def delete(self, node, num, b=1):
        if num == 0:
            node = node.next
            return node
        while node and node.next:
            if num == b:
                node.next = node.next.next
            b += 1
            node = node.next
        return node

    # 翻转
    def reverse(self, nodelist):
        list = []
        while nodelist:
            list.append(nodelist.val)
            nodelist = nodelist.next
        result = Node()
        result_handle = NodeHandle()
        for i in list:
            result = result_handle.add(i)
        return result


class Solution(object):
    def __init__(self):
        self.count = 0

    def reverse_list(self, head, n) -> Node:
        self.count += 1
        if self.count == n or n == 0 or not head:
            print("head", head)
            return head
        elif not head.next:
            return head
        headNode = self.reverse_list(head.next, n)  # 5
        head.next.next = head
        head.next = None
        return headNode


if __name__ == '__main__':
    l1 = Node()
    ListNode_1 = NodeHandle()
    l1_list = [1, 2, 3, 4, 5]
    l1_list.reverse()  # 翻转一下,下面的for是顺序添加
    for i in l1_list:
        ListNode_1.add(i)
    # print("aaa", ListNode_1.cu

 

Python 

(一)迭代

循环了n次,时间复杂度是O(n),但是只需要一遍,空间复杂度是O(1)

迭代法就是相当于假设有两个链表,其中一个链表是空的,我们要做的工作就是把当前链表的元素不断移动到空链表上。pre就是那个空链表,然后不断将当前链表移动到空链表上

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
class Solution():
    def ReverseList(self, head: ListNode) -> ListNode:
        if (head == None or head.next == None):
            return head
        pre = None
        while head:
            tmp = head.next
            head.next = pre
            pre = head
            head = tmp
        return pre

(二)递归

递归法的时间复杂度比迭代法的空间复杂度要高,虽然时间复杂度是一样的,但是递归调用需要额外的时间开销,所以第一种方法是首选,但是如果被问到有没有其他的方法,如果能够说出第二种方法,那就能够起到锦上添花的效果了。

循环了n次,时间复杂度是O(n),空间复杂度是O(N)

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        if not head.next:
            return head
        headNode = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return headNode

python递归实现链表反转的理解过程:

ListNode类不多说,Python实现链表的常用形式。重点关注reverseList( )函数的实现过程。

1.首先函数进入开头的两个if语句,分别是用来判断当前节点和下一个节点是否为NULL,尤其是第二个,在后面递归过程中也会用到。

2.然后开始进入递归,注意传给 self.reverseList( ) 的参数为 head.next ,也就是说链表的会一直往后传递,直到找到最后一个节点(也就是head.val == 5的节点,后文简述为节点5)。此时,因为不满足第二个if语句,返回节点5。

我们可以在第二个if语句中加入一行print( head.val ) ,这样可以更容易看出返回的内容。

反转链表

 反转链表

 

 

 

反转链表

 

 

 

 3.函数在第二步返回到递归的上一层,headNode 等于返回的节点5 , 也就是节点5作为反转的链表头,完成反转的第一步。

反转链表

 

 

 

4. 当前节点head为节点4 , head.next指向节点5, head.next.next指向None。 head.next.next= head 让原来指向None的节点5,改为指向节点4,完成了5—>None到5—>4的反转;然后head.next = None , 作用在于截断节点4到节点5的指针,避免形成4—>5—>4的环。

 

 反转链表

5.同理,返回上一层,当前节点head为节点3,让节点4指向节点3,再截断节点3到节点4的指针。

反转链表

 

 

 

 6.如此重复,直到反转所有节点,headNode即为反转后的链表。

 

反转链表

 

反转链表

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 Java

迭代

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

 

递归

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode node = this.reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;
    }
}

 

上一篇:重磅首发|闲鱼构建Flutter企业级应用开发电子书新鲜出炉


下一篇:Note Studio for Mac(音频笔记应用)