206. Reverse Linked List

题目描述

Reverse a singly linked list.

解题方法

紀錄pre, cur

    public ListNode reverseList(ListNode head){
        ListNode preNode = null;
        while(head != null){
            ListNode temp = head.next;
            head.next = preNode;
            preNode = head;
            head = temp;
        }
        return pre;
    }

92. Reverse Linked List II

题目描述

Reverse a linked list from positionmt on. Do it

For example:
Given1->2->3->4->5->NULL,m= 2 andn= 4,

return1->4->3->2->5->NULL.

解题方法

紀錄pre, cur

注意到nth的距離

    public ListNode reverseBetween(ListNode head, int m, int n){
        //corner case
        if( m >= n || head == null){
            return head;
        }
        if(head.next == null){
            return head;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        head = dummy;
        ListNode pre = null;        //若會轉到指定的node, 則需紀錄previous node
        for(int i = 0; i < m ; i++){
            if(head == null){       //check null status 
                return null;
            }
            pre = head;
            head = head.next;
        }

        ListNode cur = head;
        ListNode tempPre = null;
        for(int i = m; i <= n; i++){  //Range between m, n
            if(head == null){
                return null;
            }
            ListNode temp = head.next;
            head.next = tempPre;
            tempPre = head;
            head = temp;
        }

        pre.next = tempPre;
        cur.next = head;
        return dummy.next;
    }