求教关于【链表内指定区间反转】用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