单向链表反转

2021-08-28#数据结构 #链表 #单向链表

简单的链表直接反转

思路：

定义三个指针curr，pre, next分别指向当前节点，前序节点和后继节点。那么对于当前节点来说，要实现反转，就是将当前节点的后继指针指向它的前序节点即可。处理完当前节点，指针移动到下一个节点，继续执行上面操作。直到当前节点为空为止。

操作图示：

<span style="background: rgb(228, 247, 210);color: rgb(19, 82, 0);
    opacity: 1;border-radius:2em">操作实例</span> 
链表a -> b -> c
初始时{1}：pre -> null，curr -> head， next -> curr.next(b)  
&nbsp; &nbsp; 执行操作：断开a到b的指针，将a的后继节点指向null  a -> pre(pre == null)  
&nbsp; &nbsp; 形成两个单向链表 a -> null, b -> c -> null  
curr指向b{2}：pre -> a，curr -> b， next -> curr.next(c)  
&nbsp; &nbsp; 执行操作：断开b到a的指针，将b的后继节点指向a  b -> pre(pre == a)  
&nbsp; &nbsp; 形成两个单向链表 b -> a, c -> null  
curr指向c{3}：pre -> b，curr -> c， next -> curr.next(null)  
&nbsp; &nbsp; 执行操作：将c的后继节点指向b  c -> pre(pre == b)  
&nbsp; &nbsp; 形成一个单向链表 c -> b -> a

实现代码:

public Node solution(Node head) {
    
    // 定义三个指针
    Node pre = null;
    Node curr = head;
    Node next = null;
    
    while(curr != null) {
    	// 因为链表会在curr和next之间断裂，所以要先保存next
        next = curr.next;
        // 将当前节点的后继指向前序
        curr.next = pre;
        // 更新前序节点
        pre = curr;
        // 将当前指针后移
        curr = next;
    }
    
    // 这时curr == null, pre就是新链表的头
    return pre;
}

链表局部反转

面试题：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表。

示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]

思路

搜索链表，找到需要反转的区间，在区间内执行单链表反转。然后将反转后的区间链表当成一个整体嵌入到之前的链表中间即可。

图解：

和链表直接反转一样，还是先定义三个指针curr，pre, next; 分别指向当前节点，前序节点和后继节点
当curr进入反转区间时：

如上图所示，直接将curr指向pre(pre == a)。因为后面我们需要操作反转区间的开始节点和他的前序节点，所以这里将他们记录下来。

核心代码如下：

// 记录下一个游标位置
next = curr.next; 
// 更新当前节点的后继指针
curr.next = pre;

// 记录反转区间开始节点和他的前序节点
startReversePreNode = pre;
startReverseNode = curr;

curr指针抵达反转区间末尾，与上面操作一样，更新当前游标后继节点

curr.next = pre;

curr指针离开反转区间时，将startReversePreNode指向反转区间的头结点pre,将startRerverseNode指向curr节点。

核心代码：

startReversePreNode = pre;
startRerverseNode = curr

实现代码

public Node reverse(Node head, int startPos, int endPos) {
	// 定义指针
    Node curr = head;
    Node pre = null;
    Node next = null;
    Node startReverseNode = null;
    Node startReversePreNode = null;
    
    int idx = 0;
    while(curr != null){
        // 记录next
        next = curr.next;
        
        // 反转区间执行反转
        if(idx >= startPos && idx <= endPos) {
            // 处理游标刚刚进入区间的情况
            if(idx == startPos) {
                startReverseNode = curr;
                startReversePreNode = pre;
            }
        	curr.next = pre;
        }
        
        // 处理游标刚刚离开区间的情况
        if(idx == endPos + 1) {
        	// 获取新的链表头部
            if(startReversePreNode == null) {
                // 说明链表是从头部就开始反转的，新的头部不是head了, 新的头部应该是pre;
                head = pre;
            }else {
                // 将反转区间的前序节点连接到反转区间的头结点
            	startReversePreNode.next = pre;
            }
            
            // 将反转链表的尾节点连接到next
            startReverseNode.next = next;
        }
        
        // 更新游标
        pre = curr;
        curr = next;
        
        idx++;
    }
    
    return head;
}

朝花夕拾

单向链表反转

简单的链表直接反转

思路：

操作图示：

实现代码:

链表局部反转

思路

图解：

实现代码

Toc

Links

Archives

Categories

Tags