链表带环问题

import java.util.Arrays;

/**
 * Author: yiminghe
 * Date: 2008-10-17
 * Time: 14:39:23
 */
/*
删除数组指定元素
*/
public class DelChars {

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 2, 4, 5, 6, 2};
        int index = 0;
        int v = 2;
        for (int i = 0; i < array.length; i++) {
            if (v == array[i]) {
                index++;
                continue;
            }

            if (index != 0)
                array[i - index] = array[i];
        }
        System.out.println(array.length - index);
        System.out.println(Arrays.toString(array));
    }
}

 

 

/**
 * Author: yiminghe
 * Date: 2008-10-17
 * Time: 15:32:04
 */

class M_LinkNode {
    String info = "";
    M_LinkNode next = null;

    public M_LinkNode(String str_info, M_LinkNode next_) {
        this.info = str_info;
        this.next = next_;
    }
}

public class Link {

    private static int getLength(M_LinkNode head) {
        int count = 0;
        while (head.next != null) {
            count++;
            head = head.next;
        }
        return count;
    }


    /**
     * 找 链表环的 第一个元素
     */
    public static void loop() {
        //
        //1 - 2 - 3 - 4 - 5 - 2
        M_LinkNode node5 = new M_LinkNode("5", null);
        M_LinkNode node4 = new M_LinkNode("4", node5);
        M_LinkNode node3 = new M_LinkNode("3", node4);
        M_LinkNode node2 = new M_LinkNode("2", node3);
        M_LinkNode node1 = new M_LinkNode("1", node2);
        node5.next = node2;


        M_LinkNode start1 = node1;
        M_LinkNode start2 = node1;

        do {
            start1 = start1.next;
            start2 = start2.next.next;
        } while (start2.next != null && start1 != start2);

        if (start2.next == null)
            return;

        start2 = node1;
        while (start2 != start1) {
            start2 = start2.next;
            start1 = start1.next;
        }

        System.out.println(" 环的第一个结点为 : " + start1.info);
    }


    /**
     * 找出单向链表的中间结点 这道题和解判断链表是否存在环，我用的是非常类似的方法，
     * 只不过结束循环的条件和函数返回值不一样罢了。
     * 设置两个指针p1，p2。每次循环p1向前走一步，p2向前走两步。当p2到达链表的末尾时，p1指向的时链表的中间。
     */
    public static void middle() {
        M_LinkNode node4 = new M_LinkNode("4", null);
        M_LinkNode node3 = new M_LinkNode("3", node4);
        M_LinkNode node5 = new M_LinkNode("5", node3);
        M_LinkNode node2 = new M_LinkNode("2", node3);
        M_LinkNode node1 = new M_LinkNode("1", node2);
        M_LinkNode start1 = node5;
        M_LinkNode start2 = node5;

        while (start1 != null && start2.next != null) {
            start1 = start1.next;
            start2 = start2.next.next;
        }

        System.out.println("中间结点 :" + start1.info);

    }

    public static void main(String[] args) {
        loop();
    }


    /**
     * 分别遍历两个链表，得出链表长度m和n。
     * 取m和n中较小的一个，长的那个先从头前进以保证后面的长度等于较小值。
     * 两个一起走，若有相等的节点，则就是要找的节点。
     * 这个算法复杂是O(n)的，但是相当于三次遍历。
     * <p/>
     * 还想到一个空间复杂度比较大的，就是建立一个Hash表。
     * 遍历第一个链表，存各个节点
     * 遍历第二个链表，同时，判断节点是否已经保存在Hash表中了。
     * 相当于两次遍历，但空间就上去了，因为用了Hash实际性能也未见得比第一个高，只是可以安慰自己Hash可以认为是O(1)的。
     */
    public static void joinOne() {
        M_LinkNode node4 = new M_LinkNode("4", null);
        M_LinkNode node3 = new M_LinkNode("3", node4);
        M_LinkNode node5 = new M_LinkNode("5", node3);
        M_LinkNode node2 = new M_LinkNode("2", node3);
        M_LinkNode node1 = new M_LinkNode("1", node2);
        //1,2,
        //    3,4
        //   5

        int l1 = getLength(node1);
        int l2 = getLength(node5);
        int d = Math.abs(l1 - l2);
        M_LinkNode l_n = node1;
        M_LinkNode s_n = node5;
        if (l1 < l2) {
            l_n = node5;
            s_n = node1;
        }

        while (d > 0) {
            l_n = l_n.next;
            d--;

        }


        while (l_n != null && s_n != null) {
            if (l_n == s_n) break;
            l_n = l_n.next;
            s_n = s_n.next;
        }

        if (l_n == s_n) {
            if (s_n != null) {
                System.out.println("相交于 :" + s_n.info);
            }
        }

    }
}