单链表区间反转

[geosmart]

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

实现思路

1. 反转[m,n]之间的子链表：需记录m的前一个节点，n的后一个节点
2. 反转后链表插入原链表；

涉及单链表的按索引查找元素，插入，删除操作知识

代码

 public static ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //遍历指针
        ListNode cur = dummy;
        //找到m-n之间的节点，并反转
        for (int i = 1; i < m; i++) {
            cur = cur.next;
        }
        //m的后1个节点，反转后即为尾部的前一个节点
        ListNode  last = cur.next;
        //m的前1个节点
        ListNode front= cur;
        //反转的临时变量
        ListNode pre= null;
        for (int i = m; i <= n; i++) {
            cur = front.next;
            front.next = cur.next;
            cur.next = pre;
            pre= cur;
        }
        //尾部：取n的后一个节点
        cur= front.next;
        //插入反转后的链表
        front.next = pre;
        //衔接尾部
        last.next= cur;
        return dummy.next;
    }