Java算法之链表（反转链表、双节点反转链表）

亦凉 2023-07-11 15:20 49阅读 0赞

## Java算法之链表操作 ##

之前做了一些链表的算法题，感觉链表的操作比较抽象，与C++/C不同，Java当中指针的概念不是特别明确，大部分时候我们称它们为引用，可能操作起来有些难以理解，最好画出相应的图来进行说明  
下面是一道原地反转链表的解法＋图解

### 反转链表 ###

/** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */
    import java.util.ArrayList;
    public class Solution { 
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { 
            ListNode head = listNode;
            ArrayList<Integer> list = new ArrayList();
            if(listNode==null)return list;
            if(listNode.next==null)
            { 
                list.add(listNode.val);
            }
            ListNode pre = null;
            ListNode cur = listNode;
            ListNode next = null;
            while(cur!=null)
            { 
               next = cur.next;
               cur.next = pre;
               pre = cur;
               cur = next;
            }
            while(pre!=null)
            { 
                list.add(pre.val);
                pre=pre.next;
            }
            return list;
        }
    }

这题用反转链表进行的实现，分别创建三个引用pre，cur，和next代表前一个结点，当前结点和后一个结点，主要说一下while循环中引用切换的逻辑

刚开始的引用关系如下图，蓝色箭头始终代表 `cur`的`next`引用  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70]  
`next = cur.next;`让next引用指向当前结点的下一个  
![在这里插入图片描述][20200306141100304.png]  
`cur.next = pre;`当前结点的下一个已经被保存好了，所以蓝色箭头引用可以指向别处了，这时候就让它指向前一个结点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70 1]  
`pre = cur;`,`pre`引用之前指向的结点也被保存了，所以它可以指向`cur`结点了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70 2]  
`cur = next;`最后，`cur`结点引用的对象交给`pre`引用，自己要向后移动，反转下一个结点的前后关系了，向后移动之后，又进入了下一次循环

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

### 双节点反转链表 ###

最近又遇见了一个变形题，让成对地反转链表，例如  
// 输入: 1->2 ->3 ->4 ->5  
// 输出: 4->5->2->3->1

为了弄清楚链表的转来转去，决定还是原地去想想如何去做，发现可以先反转一遍，然后在反转后的链表上，成对地交换，具体如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70 4]  
解答如下：

//评测题目一: 单向链表“双节”点逆转.
    // 输入: 1->2 ->3 ->4 ->5
    // 输出: 4->5->2->3->1
    
    class ListNode{ 
        public int val ;
        public ListNode next =null;
        public ListNode(int val){ 
            this.val = val;
        }
    
    }
    
    public class Main { 
         static ListNode reverseDouble(ListNode inNode)
        { 
            ListNode resNode = null;
    
            //反转链表，是之前的方法
            ListNode pre = null;
            ListNode cur = inNode;
            ListNode next = null;
    
            while(cur!=null)
            { 
                next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            //交换节点
            cur = pre;
            //用一个前驱结点来标志一下，方便最后返回结果
            pre =new ListNode(0);
            next =null;
            resNode = pre;
            while (cur!=null&&cur.next!=null)
            { 
            //链表的交换过程，下面会解释
                next = cur.next;
                cur.next = next.next;
                pre.next = next;
                next.next=cur;
                pre = cur;
                cur = cur.next;
            }
    
            return  resNode.next;
        }
    
        public static void main(String[] args)
        { 
            ListNode tmp = new ListNode(1);
            ListNode inNode = tmp;
            for(int i = 2;i<6;i++)
            { 
                tmp.next = new ListNode(i);
                tmp = tmp.next;
            }
    
            //inNode 1 2 3 4 5
    
            ListNode res =reverseDouble(inNode);
    
            while(res!=null)
            { 
                System.out.print(res.val+" ");
                res=res.next;
            }
    
        }
    
    }

以1->2->3->4->5->6为例，假设已经反转完毕，链表变成了  
6->5->4->3->2->1，具体交换过程如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70 5]

*  为什么要弄一个值为0的pre节点？
    
     *  在中间交换过程中，说是双节点交换，其实参与交换的节点有三个，因为把后面两个节点位置倒换后，受影响的不光有后面的节点，还有前面的节点，所以要重新告诉前面的节点该指向谁
     *  方便后面直接拿结果，这也是链表反转时常用的一个方法，就是存一个不用的节点（比如说这里的Node0）的引用，用这个节点的next节点作为返回结果（比如这里的Node0.next），这样可以保证返回结果不受处理函数的影响

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020030614110974.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw==,size_16,color_FFFFFF,t_70
[20200306141100304.png]: https://img-blog.csdnimg.cn/20200306141100304.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200306141230607.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200306141246653.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200306141321311.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200306141722440.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200306143157498.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTI3Nw==,size_16,color_FFFFFF,t_70