算法-链表-链表反转（链表逆序、逆置）

谁践踏了优雅 2023-07-24 03:28 81阅读 0赞

# 算法-链表-链表反转（链表逆序、逆置） #

# 1 简单链表反转 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

## 1.2 题目描述 ##

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

输入: 1->2->3->4->5->NULL  
输出: 5->4->3->2->1->NULL

限制：

0 <= 节点个数 <= 5000

## 1.3 题解 ##

### 1.3.1 迭代 ###

#### 1.3.1.1 解题思路 ####

1.  记录当前节点head.next到nextNode，因为当前节点.next需要重新指向前一个节点
2.  将当前节点head.next指向前一个节点previousNode
3.  将前一个节点指针previousNode变动为当前节点位置head
4.  将当前节点指针head变动为nextNode指针位置
5.  最后返回previousNode，因为head最终必然指向null

#### 1.3.1.2 代码 ####

public ListNode reverseList(ListNode head) { 
        if(null == head){ 
            return null;
        }
        ListNode previousNode = null;
        ListNode nextNode = null;
        while(null != head){ 
            nextNode = head.next;
            head.next = previousNode;
            previousNode = head;
            head = nextNode;
        }
        return previousNode;
    }

#### 1.3.1.3 时间复杂度 ####

O(N)

#### 1.3.1.4 空间复杂度 ####

O(1)

### 1.3.2 递归 ###

#### 1.3.2.1 解题思路 ####

1.  记录下当前节点的下一个节点
2.  随后将当前节点的next指针置空，消除以前的正序依赖
3.  将下一个节点带入链表逆置方法，逆置完毕后将记录的下一个节点.next连接到当前节点
4.  注意，逆置时需要返回逆置后链表头结点
5.  最终得到全局链表头结点，返回即可

#### 1.3.2.2 代码 ####

public ListNode reverseList(ListNode head) { 
        // 空节点，不能逆置，返回null
        if(null == head){ 
            return null;
        }
        // 用来链表逆置后的头结点
        ListNode finalHead = null;
    
        // 保存当前节点的下一个节点
        ListNode nextNode = head.next;
        // 将当前节点的next指针置空，消除以前的正序依赖
        head.next = null;
        if(nextNode != null){ 
        // 下一个节点存在
            // 此时需要将下一个节点逆置，逆置后得到的头结点就是全局逆置后的头结点 
            finalHead = reverseList(nextNode);
            // 然后将之前保存的当前节点的下一个节点.next连接到当前节点，完成逆置
            nextNode.next = head;
        }else{ 
        // 下一个几点不存在，说明当前节点已经是末尾节点
            // 此时只需要把当前节点作为全局逆置后的头结点即可
            finalHead = head;
        }
        // 逆置完毕后，返回全局逆置后的头结点即可
        return finalHead;
    }

#### 1.3.2.3 时间复杂度 ####

O(N)

#### 1.3.2.4 空间复杂度 ####

*  O(N)  
    创建了N次指针

# 2 指定区间链表反转 #

## 2.1 题目出处 ##

https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

## 2.2 题目描述 ##

## 2.3 题解 ##

### 2.3.1 迭代+分布 ###

#### 2.3.1.1 解题思路 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

1.  构建一个虚拟头节点，在head之前
2.  先找到逆置链表的前一个元素（m-1）
3.  然后我们将m->n的这段链表逆置
4.  将逆置完成的链表接回原链表
5.  最后返回virtualHead.next

#### 2.3.1.2 代码 ####

public ListNode reverseBetween(ListNode head, int m, int n) { 
        if (null == head) { 
            return null;
        }
        if (m > n || m < 0) { 
            return null;
        }
    
        if (m == n) { 
            return head;
        }
    
        // 因为有可能m==1，所以我们虚拟一个节点在head之前
        // 这样最后的时候可直接返回virtualHead.next即可
        ListNode virtualHead = new ListNode(0);
        virtualHead.next = head;
    
        // 1.先找到逆置链表的前一个元素
        ListNode prevHead = virtualHead;
        // prevHead从head之前开始移动，移动了m-1次到了m-1处
        for(int i = 1; i < m; i++){ 
            prevHead = prevHead.next;
        }
        // 现在prevHead就是逆置链表的前一个元素
    
        // 2.然后我们将m->n的这段链表逆置
        ListNode nextNode = null;
        ListNode current = prevHead.next;
        ListNode reverse = null;
        for(int i = m; i <= n; i++){ 
            nextNode = current.next;
            current.next = reverse;
            reverse = current;
            current = nextNode;
        }
    
        // 3.现在需要将逆置完成的链表接回原链表
        // 首个逆置元素.next需要连接到最后一个逆置元素的下一个元素
        prevHead.next.next = current;
        // 首个逆置元素之前的元素.next需要连接到最后一个逆置元素
        prevHead.next = reverse;
    
        // 这里因为virtualHead是虚拟的头结点，可以考虑两种情况
        // 1.如果m==1，则virtualHead.next本来是head，已经
        // 2.如果m!=1，当然virtualHead.next指向的就是原来head
        return virtualHead.next;
    }

#### 2.3.1.3 时间复杂度 ####

O(N)

#### 2.3.1.4 空间复杂度 ####

O(1)

### 2.3.2 头插法 ###

#### 2.3.2.1 解题思路 ####

![在这里插入图片描述][20200410102123719.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 1]  
记录反转链表的前一个节点prevHead以及反转链表的首节点firstConverse，以后每次将下一个待反转节点移动到prevHead.next，而firstConverse.next记录该反转节点的next，从m到n-1，就已经完成了整个链表反转。

同时为了避免头结点就是反转首节点情况，引入虚拟头结点，在原head之前。

#### 2.3.2.2 代码 ####

public ListNode reverseBetween(ListNode head, int m, int n) { 
        if (null == head) { 
            return null;
        }
        if (m > n || m < 0) { 
            return null;
        }
    
        if (m == n) { 
            return head;
        }
    
        // 虚拟头结点，避免为空或头结点就是反转首节点情况
        ListNode virtualNode = new ListNode(0);
        virtualNode.next = head;
    
        // 反转链表的前一个节点
        ListNode prevHead = virtualNode;
        // 反转链表的首节点
        ListNode firstConverse = null;
    
        // 1.先移动到合适的prevHead和firstConverse位置
        for(int i = 1; i < m; i++){ 
            prevHead = prevHead.next;
        }
        firstConverse = prevHead.next;
    
        // 2.每次将下个反转节点移动到prevHead之后，采用头插法
        ListNode nextNode = firstConverse.next;
        for(int i = m; i < n; i++){ 
            firstConverse.next = nextNode.next;
            nextNode.next = prevHead.next;
            prevHead.next = nextNode;
            nextNode = firstConverse.next;
        }
        // 3.此时就已经将m到n的节点全部反转以及和外部链表连接外表了
        return virtualNode.next;
    }

#### 2.3.2.3 时间复杂度 ####

O(N)

#### 2.3.2.4 空间复杂度 ####

O(1)

# 参考文档 #

*  [反转链表2-分布解法][2-]
 *  [Java-双指针-头插法][Java-_-]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20230528/9ab0980ba9a84e1d862c3c0d31d59e8c.png
[20200410102123719.png]: /images/20230528/8cfcbe832db645ed9555002e746e88a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 1]: /images/20230528/cff87c50c3eb4740ae14fb9886976df0.png
[2-]: https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/ji-bai-liao-100de-javayong-hu-by-reedfan-6/
[Java-_-]: https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/java-shuang-zhi-zhen-tou-cha-fa-by-mu-yi-cheng-zho/