[数据结构与算法]206.反转链表 92.翻转链表II

206反转链表

1.转为list反转再新建链表

class Solution:
    def getlist(self,head):
        l=[]
        while head:
            l.append(head.val)
            head=head.next
        return l
    def initList(self,list):
        head=ListNode()
        p=head
        for i in list:
            new=ListNode(val=i)
            p.next=new
            p=new
        return head.next
    def reverseList(self, head: ListNode) -> ListNode:
        l=self.getlist(head)
        return self.initList(l[::-1])

2.迭代

设置两个指针储存，由curr指向prev，每次向后移动一位

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre,cur=None,head
        while cur:
        	###需要先执行head.next,保证链表按原来顺序遍历，head相当于上图中的next指针####
            head=head.next
            cur.next=pre
            pre=cur
            cur=head
        return pre

3.递归

①终止条件：只剩一个节点或没有节点时停止
②等价关系

reverse(head)=reverse(head.next)+改变head与head.next之间的指针关系

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        
        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return p

92.翻转链表II

1.转成list，用双指针翻转部分list，再创建新链表

时间空间复杂度都为O(n)

class Solution(object):
    def getlist(self,head):
        l=[]
        while head:
            l.append(head.val)
            head=head.next
        return l
    def initLinkedlist(self,list):
        head=ListNode()
        p=head
        for i in list:
            new=ListNode(val=i)
            p.next=new
            p=new
        return head.next
    def reverseBetween(self, head, left, right):
        L=self.getlist(head)
        l,r=left-1,right-1
        while l<r:
            L[l],L[r]=L[r],L[l]
            l+=1
            r-=1
        return self.initLinkedlist(L)

2.先截断，倒序，再链接

class Solution(object):
    def reverseBetween(self, head, left, right):
        dummy=ListNode(next=head)
        ###指针p储存截断位置前一个节点####
        p,pleft,pright=dummy,head,head
        ###取出需要倒序的列表片段####
        for i in range(right-left):
            pright=pright.next
        for j in range(left-1):
            p,pleft,pright=p.next,pleft.next,pright.next
        ####suc保存截断位置的下一个节点###
        suc=pright.next
        pright.next=None###截断####
        ####倒序###################
        def reverseLinkedlist(head):
            if head==None or head.next==None:
                return head
            p=reverseLinkedlist(head.next)
            head.next.next=head
            head.next=None
            return p
        #####连接截断的链表#########
        p.next=reverseLinkedlist(pleft)
        while p.next:
            p=p.next
        p.next=suc
        return dummy.next

3.头插法

在需要翻转的链表片段，每次将原来第一个节点的下一个节点插入到片段之前，然后将该节点删除

def reverseBetween(self, head, left, right):

        dummy_node = ListNode(-1)
        dummy_node.next = head
        pre = dummy_node
        for _ in range(left - 1):
            pre = pre.next

        cur = pre.next
        for _ in range(right - left):
            next = cur.next
            cur.next = next.next
            next.next = pre.next
            pre.next = next
        return dummy_node.next