牛客_将链表m到n节点间的元素进行反转_c++反转链表中m位置到n位置的元素

题目：将链表m到n节点间的元素进行反转

样例输入：a、b、c、d、e、f 6个ListNode结点的一个单链表 head（head是第一个元素）让其反转3到5

最终输出的val为  1 2 5 4 3 6    也就是3、4、5发生了反转成了5 、4、3

public class Solution2 {
    /**
     * 定义的ListNode结构体
     */
    private static class ListNode {
        int val;
        ListNode next = null;
        ListNode(int val) {
            this.val = val;
        }
    }
    public static void solution(ListNode head, int m, int n) {
        if (head == null)
            return;
        //创建一个dummy的结点val为0作为头结点
        ListNode dummy = new ListNode(0);
        //将dummy作为头结点来指向输入链表的第一个结点
        dummy.next = head;
        //定义了一个prev结点
        ListNode prev = null;
        //start结点是开始遍历链表的结点，m之前的链表结点是不用进行反转，直接输出就可以
        //最终的prev指向的是原来链表前面一部分的结束的位置，start标记开始进行反转的第一个位置
        //测试样例中的prev指向的就是b结点val为2    start指向的就是c结点 val为3
        ListNode start = head;
        for (int i=1; i<m; i++) {
            prev = start;
            start = start.next;
        }
        //从m到n这个几个结点是需要进行反转
        //其中的temp作为一个临时结点，
        // 每一次循环在temp结点前面的已经反转，再调整后续节点一直到最终temp节点指向的是第n个节点的位置，
        // 此时prev就是指向了temp反转结束
        for (int i=m; i<n; i++) {
            ListNode temp = start.next;
            start.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }
        //最终输出链表，因为一开始的时候将dummy的val设置为了0，相当于设置了一个头结点
        while (dummy.next!=null) {
            System.out.println(dummy.next.val+" ");
            dummy.next = dummy.next.next;
        }
    }
    public static void main(String[] args) {
        //测试,建立6个listnode结点对应的val依次为1、2、3、4、5、6
        //最终让3到5的位置的链表发生反转，并重新打印出反转后的元素
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(2);
        ListNode c = new ListNode(3);
        ListNode d = new ListNode(4);
        ListNode e = new ListNode(5);
        ListNode f = new ListNode(6);
        a.next=b;
        b.next=c;
        c.next=d;
        d.next=e;
        e.next=f;
        solution(a,3,5);
    }
}

打印输出：

​​​​​​

符合预期。