求教关于【链表内指定区间反转】用Java代码实现中的问题

链表小白,实在理解不了,就来求答案了!救救孩子吧!!!

第一种:

public static ListNode reverseBetweenOns (ListNode head, int m, int n) {
    // 定义虚拟头节点vir
    ListNode virtual = new ListNode(0);
    virtual.next = head;

    //反转开始前一节点&&开始节点
    ListNode preLeftHead = virtual;
    ListNode leftHead;

    for (int i = 0; i < m -1; i ++) {
        preLeftHead = preLeftHead.next;
    }
    leftHead = preLeftHead.next;

    //反转结束节点&&结束后一节点
    ListNode rightHead = preLeftHead;
    for (int i = 0; i < n - m + 1; i ++) {
        rightHead = rightHead.next;
    }
    ListNode preRightHead = rightHead.next;

    // 断开
    preLeftHead.next = null;
    rightHead.next = null;

    // 指定区间(m~n)反转
    printListNode(leftHead, "leftHead反转前链表值");  //打印反转前leftHead的值
    ListNode pre = reverseList(leftHead);
    printListNode(leftHead, "leftHead反转后链表值");  //打印反转后leftHead的值
  
    // 连接并返回
    preLeftHead.next = pre;
    leftHead.next = preRightHead;
    return virtual.next;
}

/**
 * 反转链表
 * 反转一个单链表。
 * @param head  链表头节点
 * @return   反转后的链表头节点
 */
public static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;

    ListNode pre = null;
    while (head != null) {
        ListNode next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

/**
 *  输出链表节点的值
 * @param listNode  链表头节点
 * @param split  分隔符
 */
public static void printListNode(ListNode listNode, String split) {
    int i = 1;
    while (listNode != null) {
        System.out.println("节点(" + split +")_" + i + " :" + listNode.val);
        listNode=listNode.next;
        i++;
    }
}

第二种:

public static ListNode reverseBetweenOns (ListNode head, int m, int n) {
    ... ... ...
    ... ... ...
    // 指定区间(m~n)反转
    printPreNode(leftHead);
    ListNode pre = null;
    // 反转链表
    while (leftHead != null) {
        ListNode next = leftHead.next;
        leftHead.next = pre;
        pre = leftHead;
        leftHead = next;
    }
    printPreNode(leftHead);
    ... ... ...
    ... ... ...

准备的数据:

ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
ListNode newHead = reverseBetweenOns(head, 2, 4 );

第二种leftHead是null我知道是因为上面循环。但是第一种在打印反转前后leftHead链表值的时候输出是下面这个样子。不太理解为什么leftHead在反转后会有值并且只有一个2。求教。。。。。。。。

节点(leftHead反转前链表值)_1 :2

节点(leftHead反转前链表值)_2 :3

节点(leftHead反转前链表值)_3 :4

节点(leftHead反转后链表值)_1 :2

全部评论
这个题目很经典 自己画图比较好理解
点赞 回复 分享
发布于 03-21 21:31 北京

相关推荐

评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务