最全，最简洁，java单链表反转，按k反转等

1，反转整个链表

下面的代码都没有判断头节点为空的情况，所以如果是实际开发中使用，请#####自行添加逻辑

int[] arr = {1, 123, 22, 34, 55, 6, 77, 324, 213, 11, 333, 434};
//节点对象
    static class Node {
        int content;
        Node next;
    }
Node headNode = null;
//添加节点
void addNode(int content) {
        Node node = new Node();
        node.content = content;
        node.next = headNode;
        headNode = node;
    }
//打印所有节点内容
void printNode() {
        Node p = headNode;
        while (p != null) {
            System.out.print(p.content + ", ");
            p = p.next;
        }
    }

public static void main(String[] arr) {
        int[] arr = {1, 123, 22, 34, 55, 6, 77, 324, 213, 11, 333, 434};
       for (int i = arr.length-1; i >=0; i--) {
            addNode(arr[i]);
        }
        printNode();
        System.out.println("-");
       headNode = revertNode1(headNode);
//    headNode = revertNode2(headNode);
//    headNode = revertNode3(headNode,null);
        printNode();
    }
//记录3个节点的方法，分别记录当前节点，正在操作节点，
//和下一个节点因为单链表只有一个方向，所以在断开两个节点
//的链接之前必须先把下一个节点记录一下。
Node revertNode1(Node start){
        Node pre = null;
        Node now = start;
        Node next;
        while (now != null) {
            //先记录下一个节点
            next = now.next;
        //将当前节点跟下一个节点断开，并指向上一个节点
            now.next = pre;
          //相当于移位操作，把当前节点和上一个节点向下移位
            pre = now;
            now = next;
        }
//now节点现在为null，所以pre是以前的最后一个节点，也就是新链接的头节点
        return pre;
    }
//下面两种是递归思想，递归其实就是把后面的逻辑看作一个整体，
//经典的例子就是汉诺塔游戏

Node revertNode2(Node start) {
        if (start.next == null) {
      //退出递归的条件，其实返回的就是链表最后的节点
            return start;
        } else {
//首先记录下一个节点，理由同上
            Node next = start.next;
//给当前节点的next初始化，主要是为了处理头节点问题，防止形成循环链表
            start.next = null;
//把以后的任务交给递归程序去做，返回的其实就是新的头节点
            Node newHead=revertNode2(next);
 //将下一个节点指向当前节点，实现反转
            next.next = start;
//返回头节点
            return newHead;
        }
    }
//这种递归的思想，其实是将pre节点压入了栈中，直到找到尾节点，
//然后将尾节点指向尾节点的上一个节点，开启出栈操作。

//第二种递归思想其实是将上个节点暴漏了出来，操作起来更简单
Node revertNode3(Node start,Node pre) {
        if (start.next == null) {
            start.next=pre;
            return start;
        } else {
//先记录下一个
            Node next = start.next;
//把当前节点指向上一个节点
            start.next = pre;
            return revertNode3(next,start);
        }
    }

2. 进阶-按照长度k，反转链表

这种思想是按照第一种反转方法，加上递归实现

Node revertNode4(Node start, int length) {
        Node pre = null;
        Node now = start;
        Node next;
        int i = 0;
        while (now != null && i < length) {
            next = now.next;
            now.next = pre;
            pre = now;
            now = next;
            i++;
        }
  
        if(now!=null) {
//1→2→3→4→5→6→7→8，步长为3，反转之后变成3→2→1→6→5→4→8→7，
//递归思想可以把6之后的节点当成已经翻转成功的节点，只需要考虑1和6的关系
//当前的start就是1，1的next需要指向上一个链接反转之后的头节点，即6,
            start.next = revertNode4(now, length);
        }
        return pre;
    }

3. 再进阶-按照长度k，反转链表，最后长度不够k的节点不反转

boolean isLastRevert = false;
Node revertNode6(Node start, int length) {

        Node pre = null;
        Node now = start;
        Node next;
        int i = 0;
        while (now != null && i < length) {
            next = now.next;
            now.next = pre;
            pre = now;
            now = next;
            i++;
        }
        if (isLastRevert) {
            return pre;
        }
//如果发现i没有达到步数，说明最后一次反转数量不够
        if (i == length) {
            start.next = revertNode6(now, length);
        } else {
            isLastRevert = true;
//将最后一次多反转的节点再反转过来，加个开关，防止反转整个链表
//这里比较绕的就是该传哪个节点，pre代表的是反转完成之后的头节点
//比如1→2→3→4→5→6→7→8，步长为3，反转之后变成
//3→2→1→6→5→4→8→7，pre代表8，revertNode6(pre, i)返回的头节点是7
//返回之后会继续走i==length内的逻辑
            return revertNode6(pre, i);
        }
        return pre;
    }

最后编辑于：2022.09.09 09:34:11