[Leetcode][python][Java]Reverse Linked List/Reverse Linked List II/反转链表/反转链表 II

水深无声 2022-06-06 04:54 159阅读 0赞

# Reverse Linked List #

## 题目大意 ##

翻转链表

## 解题思路 ##

必看：  
http://blog.csdn.net/autumn20080101/article/details/7607148  
**以下代码若理解不通请务必务必务必务必务必务必务必看上方网页**

还可以参考（迭代+递归）：  
https://blog.csdn.net/u011608357/article/details/36933337

## 代码 ##

### 迭代 ###

循环迭代体是：  
next = head->next;  
head->next = prev;  
prev = head;  
head = next;  
循环终止条件是：  
head == NULL

![这里写图片描述][70]

但是按照上述网页，如果写成：

lass Solution(object):  # 迭代
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            dummy = ListNode(None)
            while head:  # 终止条件是head=Null
                nextnode = head.next  # nextnode是head后面的节点
                head.next = dummy # dummy.next是Null，所以这样head.next就成为了Null
                dummy = head # head当前数组给dummy.next
                head = nextnode # head向后一位
            return dummy

会得到：

[5,4,3,2,1,None]

**最后的dummy节点会是None保留在最后**

应该写为把dummy都替换成dummy.next：

class Solution(object):  # 迭代
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            dummy = ListNode(None)
            while head:  # 终止条件是head=Null
                nextnode = head.next  # nextnode是head后面的节点（保持下个节点信息不丢）
                head.next = dummy.next # dummy.next是Null，所以这样head.next就成为了Null
                dummy.next = head # head当前数字给dummy.next
                head = nextnode # head向后一位
            return dummy.next

或者用prev代替dummy.next

class Solution(object):  # 迭代
        def reverseList(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            dummy = ListNode(None)
            prev = dummy.next
            while head:  # 终止条件是head=Null
                nextnode = head.next  # nextnode是head后面的节点
                head.next = prev # dummy.next是Null，所以这样head.next就成为了Null
                prev = head # head当前数组给dummy.next
                head = nextnode # head向后一位
            return prev

这样就成功通过。

**以后不理解先记上面的，然后再改为下面的。**

### 递归 ###

上面网页进行了解析，没怎么理解，有空下次继续。。。

## Java ##

直接上面第一个代码的思路就可以，不会有最后有null问题

public class Solution {
        public ListNode ReverseList(ListNode head) {
            if(head==null)
                return null;
            //head为当前节点，如果当前节点为空的话，那就什么也不做，直接返回null；
            ListNode pre = null;
            ListNode nextnode = null;
            while(head!=null){
                nextnode = head.next;
                head.next = pre;
                pre = head;
                head = nextnode;
            }
            return pre;
        }
    }

# Reverse Linked List II #

## 题目大意 ##

翻转指定位置的链表

## 解题思路 ##

将中间的执行翻转，再将前后接上

## 代码 ##

### 迭代 ###

class Solution(object):  # 迭代
        def reverseBetween(self, head, m, n):
            """
            :type head: ListNode
            :type m: int
            :type n: int
            :rtype: ListNode
            """
            # 例如[1,2,3,4,5]
            dummy = ListNode(-1)
            dummy.next = head
            node = dummy
            for __ in range(m - 1): # 1
                node = node.next
            prev = node.next  # prev.val = 2
            curr = prev.next  # curr.val = 3
            for __ in range(n - m):  # 翻转2次，和直接翻转全部链表不同的是，这里条件就是翻转次数，不通过head指向null判断，毕竟也不指向null，后面还有数字
                nextnode = curr.next
                curr.next = prev
                prev = curr
                curr = nextnode
            node.next.next = curr  # curr是翻转链表后面的链表
            node.next = prev  # prev是翻转链表前面的链表
            return dummy.next

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 reverseBetween(ListNode head, int left, int right) {
            // 因为头节点有可能发生变化，使用虚拟头节点可以避免复杂的分类讨论
            ListNode dummyNode = new ListNode(-1);
            dummyNode.next = head;
    
            ListNode pre = dummyNode;
            // 第 1 步：从虚拟头节点走 left - 1 步，来到 left 节点的前一个节点
            // 建议写在 for 循环里，语义清晰
            for (int i = 0; i < left - 1; i++) {
                pre = pre.next;
            }
    
            // 第 2 步：从 pre 再走 right - left + 1 步，来到 right 节点
            ListNode rightNode = pre;
            for (int i = 0; i < right - left + 1; i++) {
                rightNode = rightNode.next;
            }
    
            // 第 3 步：切断出一个子链表（截取链表）
            ListNode leftNode = pre.next;
            ListNode curr = rightNode.next;
    
            // 注意：切断链接
            pre.next = null;
            rightNode.next = null;
    
            // 第 4 步：同第 206 题，反转链表的子区间
            reverseLinkedList(leftNode);
    
            // 第 5 步：接回到原来的链表中
            pre.next = rightNode;
            leftNode.next = curr;
            return dummyNode.next;
        }
    
        private void reverseLinkedList(ListNode head) {
            // 也可以使用递归反转一个链表
            ListNode pre = null;
            ListNode cur = head;
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
        }
    }

# 总结 #

链表难在理解，经典题目。这里整理的解法都是容易理解的，好好看吧。

[70]: /images/20220606/d6b4e106a3d4497285a295a006c0b96c.png