LeetCode刷题之链表

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

题解：

class Solution {
    /**
     * 思路：
     * 创建一个新头节点preNode，比较l1和l2，preNode指向小的节点
     * 然后将小的节点往后移动一个，将preNode往后移动一个，继续比较l1和l2
     * 直到l1或者l2某一个为null，那么一种一个合并完，然后将preNode指向另一个非空节点
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode preNode = new ListNode(-1);
        ListNode head = preNode;
        while (l1!=null && l2!=null) {
            if (l1.val <= l2.val) {
                //取l1的节点作为新节点的首节点
                preNode.next = l1;
                //往后移动节点
                l1 = l1.next;
            } else {
                //取l2的节点作为新节点的首节点
                preNode.next = l2;
                //往后移动节点
                l2 = l2.next;
            }
            //preNode往后移以用来保存新的节点
            preNode = preNode.next;
        }
        //当某个链表为空，非空链表剩下节点拼接在head链表的末尾
        preNode.next = l1==null?l2:l1;

        return head.next;
    }
}

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

题解：

public class Solution {
    //创建两个指针 pApA 和 pBpB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。
    //当 pApA 到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pBpB 到达链表的尾部时，将它重定位到链表 A 的头结点。
    //若在某一时刻 pApA 和 pBpB 相遇，则 pApA/pBpB 为相交结点。
    //为什么这种方法是可行的，因为当A、B都走到公共节点的时候，正好走了自己的路，又走了对方的路，两个指针走的距离相等
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode n1 = headA;
        ListNode n2 = headB;
        while(n1 != n2) {
            if(n1 != null) {
                //有后面节点，继续往后移动
                n1 = n1.next;
            } else {
                n1 = headB;
            }

            if(n2 != null) {
                n2 = n2.next;
            } else {
                n2 = headA;
            }
        }

        //当n1==n2了，即各自走了一圈半到了第一个相交节点，返回n1或n2都可以
        return n1;
    }

}

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

题解：

    public boolean isPalindrome(ListNode head) {
        //思路：采用双指针法：将链表的各个值存放到集合中，
        //启动start、end位置，前后对应对比数值看是否相等，再依次往中间靠，直到start、end相等
        ArrayList data = new ArrayList();
        while(head != null) {
            data.add(head.val);
            head = head.next;
        }
        int start = 0, end = data.size()-1;
        while(start < end) {
            if(data.get(start) == data.get(end)) {
                start++;
                end--;
            } else {
                return false;
            }
        }
        return true;
    }