反转链表2:
intel笔试题,给出指定区间,反转链表,给出指定值,如果该区间存在该值,删除它。
其实就是这题的变形,这题会了,这个笔试题也可以拿下了!
/**
* 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) {
//intel 笔试题,有缘人,如果看到了这里,你应该多写题,这样考试时候才自信拿下
// 定义一个dummyHead, 方便处理
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode leftNode = dummyHead;
ListNode rightNode = dummyHead;
while(left > 1){//不是从0开始数,//这里为什么是1 , 因为我从head 前面一位开始数的。我要先找到先驱节点
leftNode = leftNode.next;
left--;
}
//left的前驱节点保留。leftPre
ListNode leftPre = leftNode;
//left的节点
leftNode = leftNode.next;
while(right > 0){ //这里为什么是0 , 因为我从head 前面一位开始数的。
rightNode = rightNode.next;
right--;
}
// 断开后续链表;先保存临时的
ListNode temp = rightNode.next;
rightNode.next = null; // 断开联系
leftPre.next = null; // 断开前驱联系
reverseNode(leftNode);
// 接上前续
leftPre.next = rightNode;
// 接上后续
leftNode.next = temp;
return dummyHead.next; //时间复杂度O(N), 空间复杂度O(N)
}
private ListNode reverseNode(ListNode head){
//反转一个链表
if(head == null || head.next == null){
return head;
}
ListNode cur = reverseNode(head.next);
head.next.next = head;
head.next = null;
return cur;
}
}
这种方法面试官会让你优化空间。O(1)
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 定义一个dummyHead, 方便处理
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode pre = dummyHead;
// 找到前驱节点
for (int i = 0; i < left - 1; i++) { // 假如left == 2, i = 0 走1次, pre 指向第一个元素,刚刚好是left == 2 的前一个个
pre = pre.next;
}
// 找到左节点
ListNode leftNode = pre.next;
ListNode next;
// 头插法, 把left 后面的元素插入pre 后面。
for (int i = 0; i < right - left; i++) {
next = leftNode.next; // 临时保存一下,别丢弃了
leftNode.next = next.next;//跳过next , 相当于删除了后一个元素。
next.next = pre.next; // 把left 后面的元素插入pre 后面, 这个时候指向pre.next
pre.next = next; // 把pre的后置指针改变位置, 指向next ,完成一次 头插,,left后面的元素插入pre后面了。
}
return dummyHead.next;
}
}
用手画一个链表的指针,改变指针时候要先保留指针后面的值哦。
next = leftNode.next ; // 临时保存一下,别丢弃了