链表小题练手

链表小题练手

[TOC]

1 . 合并两个有序链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

示例1

输入：

{1,3,5},{2,4,6}

返回值：

{1,2,3,4,5,6}

示例2

输入：

{},{}

返回值：

{}

思路

定一个哨兵节点 newHead 如果 L1 当前节点的值小于等于 L2 ，我们就把 L1 当前的节点接在 tmp 节点的后面，同时将 L1 指针往后移一位。否则，我们对 L2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 cur 向后移一位。当L1、L2都不为空时需要比较当前第一个结点大小最后，会出现L1不为空或L2不为空，另一个为空，把剩下的结点接上(后面的次序不需要再变动了)

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
             ListNode newHead = new ListNode(-1);
             ListNode tmp = newHead;
             while(list1!=null&&list2!=null){
                 if(list1.val < list2.val){
                       tmp.next = list1;
                       list1 = list1.next;
                 }else{
                      tmp.next = list2;
                      list2 = list2.next;
                 }
                 tmp = tmp.next;
             }
             if(list1 != null){
                 tmp.next = list1;
             }
             if(list2 != null){
                 tmp.next = list2;
             }
             return newHead.next;
    }
}

2 . 删除排序链表中的重复元素

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例1：

​

输入：head = [1,1,2]
输出：[1,2]
示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

思路

指针 cur 指向链表的头节点，随后开始对链表进行遍历。如果当前 cur 与 cur.next 对应的元素相同，那么我们就将 cur.next 从链表中移除；否则说明链表中已经不存在其它与cur 对应的元素相同的节点，因此可以将 cur 指向 cur.next。

当遍历完整个链表之后，我们返回链表的头节点即可。

注意：cur.next 为空节点，如果不加以判断，访问cur.next 对应的元素会产生运行错误。因此我们只需要遍历到链表的最后一个节点，而不需要遍历完整个链表。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        if(head == null){
            return null;
        }
        while(cur.next!=null){
            if(cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;
    }
}