Intel面试官:再给你一次反转链表的机会Java

反转链表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; // 临时保存一下，别丢弃了