链表小题练手
[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;
}
}