Day 34
题目描述
思路如下
首先解释一下如何原地反转链表，就题目所示
1-》2-》3-》4-》5
将2，3，4进行反转
1-》2-》《-3《-4 5
然后将1指向4 2指向5
1-》4-》3-》2-》5，就完成了反转
具体思路可以看代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {if(left==right){//左右都是同一元素不用处理return head;}ListNode fakehead=new ListNode();fakehead.next=head;//增加一个空的头结点，目的在于防止头结点找不到其前面的节点int i=0;ListNode tes=fakehead;while(i<left-1){tes=tes.next;i++;}//找到左边反转区间的前一个元素ListNode beg=tes;tes=tes.next;//指向反转区间的第一个元素i++;if(i+1==right){//如果反转区间只有两个元素ListNode end=tes.next.next;tes.next.next=tes;beg.next=tes.next;tes.next=end;}else{//说明区间内大于两个元素ListNode before=tes;tes=tes.next;//指向反转区间的第二个元素i++;while(i!=right){ListNode xia=tes.next;//将该节点的下一个序号记录下tes.next=before;//将该节点的下一个序号指向前一个元素before=tes;//将前一个元素更新为该元素tes=xia;//移动到下一个元素i++;}//此时tes指向反转区间的最后一个元素ListNode end=tes.next;//反转区间外右边的第一个元素tes.next=before;ListNode sm=beg.next;//取出反转区间左边的第一个元素sm.next=end;beg.next=tes;}return fakehead.next;}
}
