博客

给定一个单向链表, 反转指定范围内的节点

链表反转的大致思路

反转链表只需要不断地将当前节点的下一个节点的 next 指向当前节点, 然后将下个节点设置为当前节点,

设置两个引用, cur, next 分别指向当前和下一个节点

如图所示: cur–>1, next–>2

反转操作为:

next.next-->cur


然后移动

cur

,

next


一次反转后: 当前为2, 下一个为3



循环操作, 就完成了所有的反转

指定范围的链表反转

和全部反转一样, 相当于把链表分为了三段, 反转中间那段, 再将三段连接起来

所以只需要将反转范围的前一个节点

1

和 反转范围内第一个节点

2

(反转后的最后一个) 引用保存下来, 用于反转后的连接. 然后对中间的进行反转

反转操作完成后

所以最后需要让节点

1

指向

cur

,

2

指向

next

, 就完成了

以下是代码:

public class ReverseLink {


    private static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {

        // 初始化链表
        Node head = new Node(0);
        Node cur;
        Node last = head;
        for (int i = 1; i < 15; i++) {
            cur = new Node(i);
            last.next = cur;
            last = cur;
        }

        printLink(head);
        // 反转
        Node reversed = reverse(head, 3, 5);
        printLink(reversed);

    }

    /**
     * 反转从 begin 到 end 范围的节点
     * @param node 链表头结点
     * @param begin 开始的位置
     * @param end 结束位置
     * @return 返回链表头结点
     */
    private static Node reverse(Node node, int begin, int end) {

        Node bNode = null;      // 记录反转开始的前一个
        Node eNode = null;      // 记录反转开始的第一个, 即反转的最后一个
        Node cur = node;
        
        // 找到开始反转的位置
        for (int i = 0; i < begin - 1; i++) {
            if (cur == null) {
                return node;
            }
            bNode = cur;
            cur = cur.next;
        }
        eNode = cur;

        Node nNode = cur.next;      // 下一个
        Node nnNode = null;        // 下下个
        // 进行反转
        for (int i = 0; i < end - begin; i++) {
            if (nNode != null) {
                nnNode = nNode.next;      // 先保存下下个的引用
                nNode.next = cur;       // 下一个指向当前的 (反转)
                cur = nNode;            // 移动cur, 指向下一个
                if (nnNode == null) {
                    break;
                }
                nNode = nnNode;
            }
        }

        // 将反转后的链表和两端连接
        bNode.next = cur;
        eNode.next = nnNode;

        return node;
    }


    /**
     * 打印链表节点值
     * @param head
     */
    private static void printLink(Node head) {
        while (head != null) {
            System.out.print(head.value + " -> ");
            head = head.next;
        }
        System.out.println();
    }
}

运行结果贴一下:

// 反转前
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 

// 反转后
0 -> 1 -> 4 -> 3 -> 2 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 ->