2018-08-15 LeetCode旋转链表反转链表

反转链表原型

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
        //方法二 递归
        // if(head==null || head.next==null){
        //     return head;
        // }
        // ListNode h = reverseList(head.next);
        // head.next.next = head;
        // head.next = null;
        // return h;
    }
}

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
遍历链表统计链表长度的同时记录尾节点的位置

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head==null||head.next==null||k==0)
            return head;
        int n=0;
        ListNode cur = head, tail=head;
        while(cur != null){
            n++;
            tail = cur;
            cur = cur.next;
        }
        k = n - k % n;
        if(k == n) return head;
        cur = head;
        while(--k > 0){
            cur = cur.next;
        }
        ListNode newHead = cur.next;
        cur.next = null;
        tail.next = head;
        return newHead;
    }
}

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;        
        for (int i = 0; i < m-1; i++){
            first = first.next;
        }
        ListNode cur = first.next;        
        for (int i = 0; i<n-m; i++){
            ListNode node = cur.next;
            cur.next = node.next;
            node.next = first.next;
            first.next = node;          
        }        
        return dummy.next;        
    }
}