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