07、数据结构与算法 - 实战：单链表2

题目1：假设两个单向链表在某结点相交后，成为一个新的单向链表。两个链表的头结点是已知的，但是相交的结点未知。也就是说，它们相交之前的结点个数是未知的，并且两个链表的结点数也可能不同。假设链表List1和链表List2在相交之前的结点个数分别为n和m，那么m可能等于或小于n,也可能大于n。找出两个链表的合并点。
思路：
 1.先获取两个链表的长度（假设List1的长度为m,List2的长度为n，m > n）
 2.计算两个链表的长度差 d = m - n
 3.从较长的链表（List1）的表头开始，移动d个结点
 4.两个链表同时移动，直至出现两个后继指针的值相等的情况

/**
 * 找出两个链表的合并点
 * @param list1  链表1
 * @param list2  链表2
 * @return 合并点
 */
public static ListNode findIntersectingNode(ListNode list1, ListNode list2) {
    // 先获取两个链表的长度
    int m = LinkedList.getLength(list1);
    int n = LinkedList.getLength(list2);
    // 计算长度的差值,并确定长链表和短链表
    int diff = 0;
    ListNode headOfLongList = null;
    ListNode headOfShortList = null;
    if (m < n) {
        diff = n - m;
        headOfLongList = list2;
        headOfShortList = list1;
    } else {
        diff = m - n;
        headOfLongList = list1;
        headOfShortList = list2;
    }
    // 长链表移动diff个结点
    for (int i = 0; i < diff; i++) {
        headOfLongList = headOfLongList.getNext();
    }
    // 两个链表一起移动，寻找合并点
    while (headOfLongList != null && headOfShortList != null) {
        headOfLongList = headOfLongList.getNext();
        headOfShortList = headOfShortList.getNext();
        // 如果找到直接返回
        if (headOfLongList == headOfShortList) {
            return headOfLongList;
        }
    }
    // 两个链表没有合并点
    return null;
}

题目：如何找到链表的中间结点
思路1：
遍历链表，得到链表的长度；定位到第n/2个结点，即中间结点。

/**
 * 如何找到链表的中间结点
 * @param headNode 链表的头结点
 * @return 链表的中间结点
 */
public static ListNode findMiddleNode1(ListNode headNode) {
    // 获取链表的长度
    int length = LinkedList.getLength(headNode);
    // 定位到第n/2个结点，即中间结点
    ListNode middleNode = LinkedList.getNodeByPosition(headNode, length/2);
    return middleNode;
}

 思路2：
 使用两个指针fastPtr和slowPtr，两个指针同时从头结点出发，并使fastPtr移动速度是slowPtr移动速度的两倍。当fastPtr移动到链表的尾结点时，slowPtr指向的结点就是中间结点

/**
 * 如何找到链表的中间结点
 * @param headNode 链表的头结点
 * @return 链表的中间结点
 */
public static ListNode findMiddleNode2(ListNode headNode) {
    // 定义两个指针
    ListNode fastPtr = headNode;
    ListNode slowPtr = headNode;
    // 同时移动，并使fastPtr移动速度是slowPtr移动速度的两倍，需要判断尾结点
    int i = 0;
    while (fastPtr.getNext() != null) {
        if (i == 0) {
            // fastPtr指针先移动一个结点
            fastPtr = fastPtr.getNext();
            i = 1;
        } else if (i == 1) {
            // 两个指针同时移动一个结点
            fastPtr = fastPtr.getNext();
            slowPtr = slowPtr.getNext();
            i = 0;
        } 
    }
    // 返回中间结点
    return slowPtr;
}

题目:检查链表的长度是奇数还是偶数
思路1：先获取链表的长度，对链表的长度进行奇偶判断

/**
 * 检查链表的长度是奇数还是偶数
 * @param headNode 链表的头结点
 * @return true 是偶数 false 是奇数
 */
public static boolean isEven1(ListNode headNode) {
    // 先获取链表的长度
    int length = LinkedList.getLength(headNode);
    // 对长度进行奇偶判断
    if (length % 2 == 0) {
        return true;
    }
    return false;
}

 思路2：
 使指针指向链表的头结点，指针每次移动两个结点。如果最后指针指向null，说明链表长度是偶数；否则就是指向尾结点，长度为奇数。

/**
 * 检查链表的长度是奇数还是偶数
 * @param headNode 链表的头结点
 * @return true 是偶数 false 是奇数
 */
public static boolean isEven2(ListNode headNode) {
    while (headNode != null && headNode.getNext() != null) {
        headNode = headNode.getNext().getNext();
    }
    if (headNode == null) {
        return true;
    }
    return false;
}

题目：将两个有序链表合并为一个新的有序链表
思路1：先获取两个链表的长度，保持长的链表不动，对短的链表遍历，一个一个的插入的新的链表

/**
 * 将两个有序链表合并为一个新的有序链表
 * @param list1  有序链表
 * @param list2  有序链表
 * @return 合并后新的链表
 */
public static ListNode mergeList1(ListNode list1, ListNode list2) {
    // 判断链表是否存在
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    // 先获取两个链表的长度
    int m = LinkedList.getLength(list1);
    int n = LinkedList.getLength(list2);
    // 对比链表长度,确定长链表和短链表
    ListNode headOfLongList = null;
    ListNode headOfShortList = null;
    if (m < n) {
        headOfLongList = list2;
        headOfShortList = list1;
    } else {
        headOfLongList = list1;
        headOfShortList = list2;
    }
    // 遍历短的链表并插入长的链表中
    ListNode newHeadNode = headOfLongList;
    ListNode previousNode = null;
    ListNode currentNode = null;
    while (headOfLongList != null && headOfShortList != null) {
        if (headOfLongList.getData() <= headOfShortList.getData()) {
            previousNode = headOfLongList;
            headOfLongList = headOfLongList.getNext();
            continue;
        }
        // 找到需要插入的结点，并将短链表移动一个结点
        currentNode = headOfShortList;
        headOfShortList = currentNode.getNext();
        // 向长链表插入短链表的结点
        previousNode.setNext(currentNode);
        currentNode.setNext(headOfLongList);
    }
    return newHeadNode;
}

思路2：利用递归实现

/**
 * 将两个有序链表合并为一个新的有序链表
 * @param list1  有序链表
 * @param list2  有序链表
 * @return 合并后新的链表
 */
public static ListNode mergeList2(ListNode list1, ListNode list2) {
    ListNode result = null;
    // 判断链表是否存在
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    if (list1.getData() <= list2.getData()) {
        result = list1;
        result.setNext(mergeList2(list1.getNext(), list2));
    } else {
        result = list2;
        result.setNext(mergeList2(list1, list2.getNext()));
    }
    return result;
}