链表 2016-09-06

[wolfogre]

92. Reverse Linked List II

142. Linked List Cycle II

[dayang]

/**
 * [AC] LeetCode 92. Reverse Linked List II
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} m
 * @param {number} n
 * @return {ListNode}
 */
var reverseBetween = function(head, m, n) {
    var i, mid = Math.floor((m + n) / 2), leftPart = [],p = head,temp;
    for(i = 1;i <= n; i++,p = p.next){
        if(i >= m && i <= mid){
            leftPart.push(p);
        }else if(i > mid){
            temp = p.val;
            p.val = leftPart[n-i].val;
            leftPart[n-i].val = temp;
        }
    }
    return head;
};

[dayang]

/**
 * [AC] LeetCode 142. Linked List Cycle II
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    if(head === null || head.next === null) return null;
    var slow = head.next,fast = head.next.next;
    while(fast !== null && fast !== slow && fast.next !== null){
        slow = slow.next;
        fast = fast.next.next;
    }
    if(slow !== fast) return null;
    slow = head;
    while(slow !== fast){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
};

[zhaokuohaha]

92 - C

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode ReverseBetween(ListNode head, int m, int n) {
        if(m==n || head == null) return head;
        ListNode nullHead = new ListNode(0);
        nullHead.next = head;
        ListNode p = head;
        ListNode pre = nullHead;
        for(int i=1; i<m; i++){
            pre = p;
            p = p.next;
        }
        pre.next = null;
        ListNode q, first = p;
        for(; m<=n; m++){
            q = pre.next;
            pre.next = p;
            p = p.next;
            pre.next.next = q;
        }
        first.next = p;
        return nullHead.next;
    }
}

意思一样的java代码, 那一段转换代码好神奇

public ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dumy = new ListNode(Integer.MIN_VALUE);
    dumy.next = head;

    ListNode begin = dumy;
    for (int i = 1; i < m; i++) {
        begin = begin.next;
    }

    ListNode cur = begin.next;
    for (int i = m; i < n; i++) {
        ListNode temp = cur.next.next;
        cur.next.next = begin.next;
        begin.next = cur.next;
        cur.next = temp;
    }

    return dumy.next;
}

[zhaokuohaha]

142 - C# - 初始化: 各走一步啊!!!

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode DetectCycle(ListNode head) {
        if(head==null || head.next == null) return null;
        ListNode fast = head.next.next,slow=head.next;
        while(fast != null && fast.next != null && fast != slow){
            fast = fast.next.next;
            slow = slow.next;
        }
        if(slow != fast) return null;
        slow = head;
        while(slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}