Python 연결리스트의 반전 방법은 무엇입니까?-파이썬 튜토리얼-php.cn

Python 연결리스트의 반전 방법은 무엇입니까?

WBOY

풀어 주다： 2023-04-29 22:55:11

앞으로

1934명이 탐색했습니다.

Python Linked List 반전

Reverse linked list

은 단일 연결 목록의 헤드 노드 헤드를 제공합니다. 연결 목록을 반전하고 역방향 연결 목록을 반환하세요.

Python 연결리스트의 반전 방법은 무엇입니까?

입력: 머리 = [1,2,3,4,5]
출력: [5,4,3,2,1]

Python 연결리스트의 반전 방법은 무엇입니까?

입력: head = [1,2]
output : [2,1]

예제 3 :

input : head = []
output : []

solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    """
    解题思路：
    1.新建一个头指针
    2.遍历head链表，依次在新的头节点位置插入，达到反转的效果
    """
    def reverseList(self, head: ListNode) -> ListNode:
        # 循环
        new_head = None

        while head:
            per = head.next # pre 为后置节点，及当前节点的下一个节点

            head.next = new_head # 插入头节点元素

            new_head = head # 把串起来的链表赋值给头指针

            head = per  # 向后移一个单位
        
        return  new_head  # 返回一个新的链表

로그인 후 복사

연결 목록 역방향을 위한 Python 관련 팁

단일 연결 목록의 헤드 노드 pHead를 고려하면(헤드 노드는 값을 갖습니다. 예를 들어 아래 그림에서 값은 1입니다), 길이는 n입니다. 연결 목록을 뒤집으면 새 연결 목록의 헤더가 반환됩니다.

요구 사항: 공간 복잡도 O(1)O(1), 시간 복잡도 O(n)O(n).

Python 연결리스트의 반전 방법은 무엇입니까?

입력:

{1,2,3}

반환값:

{3,2,1}

가장 기본적인 역방향 연결리스트 코드를 먼저 살펴보겠습니다.

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # write code here
        cur = pHead
        pre = None
        while cur:
            nextNode = cur.next
            cur.next = pre
            pre = cur
            cur = nextNode
        return pre

로그인 후 복사

핵심 공식

은 몇 가지 핵심 사항을 포착합니다.

cur: 원래 연결 목록의 헤드 노드 반전이 끝나면 cur는 pre
pre의 다음 노드를 가리킵니다. 원래 연결 리스트의 헤드 노드, 즉 역방향 연결 리스트의 헤드 노드입니다. 최종 반환은 pre입니다.
while cur: 루프를 반전시키는 조건을 나타냅니다. 여기서는 cur가 비어 있는지 여부를 판단합니다. 질문
의 조건에 따라 다른 루프 조건으로 변경하여 연결 리스트의 꼬리 노드를 반전시킬 수도 있습니다. 여기서 꼬리 노드는 None이며 명시적인 지정은 나중에 언급됩니다.

연결리스트 역방향 문제는 원본 연결리스트의 선두 노드, 원본 연결리스트의 꼬리 노드, 역방향 루프 조건, 그리고 역방향 연결리스트의 꼬리 노드.

다음으로 두 가지 예를 들어보겠습니다.

연결된 목록에서 지정된 간격을 반전합니다.

연결된 목록에서 모든 k 노드를 반전합니다.

연결된 목록에서 지정된 간격을 반전합니다.

연결된 목록에서 지정된 간격을 반전합니다. 연결된 리스트를 m 크기로 변환하려면 위치와 n 위치 사이의 간격 역전에는 시간 복잡도 O(n)과 공간 복잡도 O(1)이 필요합니다.

요구 사항: 시간 복잡도 O(n), 공간 복잡도 O(n)

고급: 시간 복잡도 O(n), 공간 복잡도 O(1)

입력:

{1 ,2,3, 4,5},2,4

반환값:

{1,4,3,2,5}

공식 적용

이 질문과 기준의 차이점은 , 입니다. 전체 연결 목록의 반전을 연결 목록의 m 위치와 n 위치 사이의 간격 반전으로 변경합니다. 공식을 적용해 보겠습니다.

원래 연결 목록의 헤드 노드: cur: head에서 시작 그리고 m-1 단계로 가서 cur
에 도달합니다. 원래 연결 리스트의 꼬리 노드: pre: cur
앞의 노드: 역방향 루프 조건: for i in range(n,m)
링크드 리스트의 테일 노드 반전: 필수 헤드부터 저장하고, 다시 m-1걸음 진행하고, cur에 도달하면 이때 pre의 위치는 prePos입니다. prePos.next는 역연결 리스트

의 테일 노드입니다. 특히 주의가 필요합니다.

헤드부터 다시 m-1단계를 거쳐 저장해야 합니다. cur에 도달하면 이때 pre locationprePos. 역방향 루프가 끝난 후 스레드를 다시 통과합니다
전체 연결 목록이 역전되지 않으므로 새로운 가상 헤드 노드 dummyNode를 만드는 것이 가장 좋습니다. dummyNode.next는 전체 연결 목록을 가리킵니다

Python 연결리스트의 반전 방법은 무엇입니까?

코드 구현

먼저 수식 부분의 코드를 살펴보겠습니다:

# 找到pre和cur
i = 1
while i<m:
    pre = cur
    cur = cur.next
    i = i+1
 
# 在指定区间内反转
preHead = pre
while i<=n:
    nextNode = cur.next
    cur.next = pre
    pre = cur
    cur = nextNode
    i = i+1

로그인 후 복사

코드의 바늘 부분 스레딩:

nextNode = preHead.next
preHead.next = pre
if nextNode:
    nextNode.next = cur

로그인 후 복사

전체 코드:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class Solution:
    def reverseBetween(self , head , m , n ):
        # write code here
        dummpyNode = ListNode(-1)
        dummpyNode.next = head
        pre = dummpyNode
        cur = head
 
        i = 1
        while i<m:
            pre = cur
            cur = cur.next
            i = i+1
 
        preHead = pre
        while i<=n:
            nextNode = cur.next
            cur.next = pre
            pre = cur
            cur = nextNode
            i = i+1
        
        nextNode = preHead.next
        preHead.next = pre
        if nextNode:
            nextNode.next = cur
 
        return dummpyNode.next

로그인 후 복사

k 그룹마다 연결된 목록의 노드를 뒤집습니다

K개의 그룹으로 주어진 연결리스트의 노드를 뒤집고, 뒤집힌 연결리스트를 반환합니다.

연결리스트의 노드 수가 k의 배수가 아닌 경우 마지막 남은 노드를 그대로 유지합니다

수 없습니다. 노드의 값을 변경하고 노드 자체만 변경합니다.

에는 공간 복잡도 O(1), 시간 복잡도 O(n)

이 필요합니다. 입력:

{1,2,3,4,5},2

반환 값:

{ 2, 1,4,3,5}

공식 적용

이 질문과 기준의 차이점은 노드 수가 다음과 같을 경우 전체 연결 리스트의 반전이 k개의 반전 그룹으로 변경된다는 점입니다. k의 배수가 아니고 나머지 노드는 그대로 둡니다.

먼저 섹션별로 살펴보겠습니다. 위치 1에서 위치 k까지 연결 목록이 있다고 가정합니다.

원래 연결 목록의 헤드 노드: cur: 머리에서 시작하여 cur에 도달하려면 k-1 단계를 수행합니다.
原链表的尾节点：pre：cur前面的节点
反转循环条件：for i in range(1,k)
反转链表的尾节点：先定义tail=head，等反转完后tail.next就是反转链表的尾节点

先看下套公式部分的代码：

pre = None
cur = head
tail = head
 
 
i = 1
while i<=k:
    nextNode = cur.next
    cur.next = pre
    pre = cur
    cur = nextNode
    i = i+1

로그인 후 복사

这样，我们就得到了1 位置1-位置k的反转链表。

此时：

pre：指向反转链表的头节点
cur：位置k+1的节点，下一段链表的头节点
tail：反转链表的尾节点

那么，得到位置k+1-位置2k的反转链表，就可以用递归的思路，用tail.next=reverse(cur，k)

需要注意：如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样

i = 1
tmp = cur
while i<=k:
    if tmp:
        tmp = tmp.next
    else:
        return head
    i = i+1

로그인 후 복사

代码实现

完整代码：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
class Solution:
    def reverseKGroup(self , head , k ):
       
        # write code here
        return self.reverse(head, k )
    
    def reverse(self , head , k ):
        pre = None
        cur = head
        tail = head
 
        i = 1
        tmp = cur
        while i<=k:
            if tmp:
                tmp = tmp.next
            else:
                return head
            i = i+1
        
        i = 1
        while i<=k:
            nextNode = cur.next
            cur.next = pre
            pre = cur
            cur = nextNode
            i = i+1
 
        tail.next = self.reverse(cur, k)
        return pre

로그인 후 복사

好了，抓住几个关键点：