算法问题——链表

    /**
     * 删除的指定的元素 利用一个指针来实现
     *
     * @param head
     * @return
     */
    public ListNode deletenodevalue(ListNode head, int targe) {
        ListNode dumy = new ListNode(0);
        dumy.next = head;
        ListNode curr = dumy;

        while (curr.next != null) {
            if (curr.next.val == targe) {
                curr.next = curr.next.next;
                continue;
            }
            curr = curr.next;
        }

        return dumy.next;

    }
    /**
     * 删除的指定的元素 利用两个指针来实现
     *
     * @param head
     * @return
     */
    public ListNode deletenodevalue2(ListNode head, int targe) {
        //初始化一个虚拟节点
        ListNode dummy = new ListNode(0);
        //让虚拟节点指向头结点
        dummy.next = head;
        ListNode cur = head;
        ListNode pre = dummy;
        while (cur != null) {
            if (cur.val == targe) {
               cur=cur.next;
               pre.next=cur;
               continue;
            }else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        //最后返回虚拟节点的下一个结点即可
        return dummy.next;
    }

/**
 * Copyright (C), 2018-2020
 * FileName: 指定区间链表翻转
 * Author:   xjl
 * Date:     2020/9/16 14:46
 * Description:
 */
package 牛客面试必会100题;

public class 指定区间链表翻转 {

    public static class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 将一个链表 m\ m m 位置到 n\ n n 位置之间的区间反转，要求时间复杂度 ，空间复杂度 。
     * 例如：
     * 给出的链表为 1→2→3→4→5→NULL1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, ，,
     * 返回 1→4→3→2→5→NULL1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL.
     *
     * @param head
     * @param m
     * @param n
     * @return
     */
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dumpy = new ListNode(-1);
        dumpy.next = head;

        ListNode frist = dumpy;
        int a = m - 1;
        while (a > 0) {
            frist = frist.next;
            a--;
        }
        ListNode node = frist.next;
        frist.next = null;

        ListNode second = node;
        int num = n - m;
        while (num > 0) {
            second = second.next;
            num--;
        }
        ListNode node1 = second.next;
        second.next = null;
        //合起来
        ListNode res = reverse(node);
        ListNode next = res;

        while (next.next != null) {
            next = next.next;
        }
        frist.next = res;
        next.next = node1;
        return dumpy.next;
    }

    public static ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode future = curr.next;
            curr.next = pre;
            pre = curr;
            curr = future;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode s1 = new ListNode(1);
        ListNode s2 = new ListNode(2);
        ListNode s3 = new ListNode(3);
        ListNode s4 = new ListNode(4);
        ListNode s5 = new ListNode(5);

        s1.next = s2;
        s2.next = s3;
        s3.next = s4;
        s4.next = s5;

        ListNode listNode = reverseBetween(s1, 2, 4);
        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}