Linkedlist-Easy

Abstract： 更新部分Easy难度 Linkedlist相关题解

21. Merge Two Sorted Lists

解法一：递归法

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null)return l2;
        else if(l2==null)return l1;
        else if(l1.val<l2.val){
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
            }
        else {
            l2.next=mergeTwoLists(l2.next,l1);
            return l2;
        }
    }
}

解法二：迭代法

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode pre_head=new ListNode(-1);  //合并结果的头结点，pre_head.next开始为答案
        ListNode curr=pre_head;              //指向当前访问节点
        while(l1!=null && l2!=null){
            if(l1.val<l2.val){               //根据大小判断先放谁
                curr.next=l1;
                l1=l1.next;
            }
            else {
                curr.next=l2;
                l2=l2.next;
            }
            curr=curr.next;
        }
        curr.next=l1==null?l2:l1;           //当一方为null时，另一方的剩余部分放入解的尾部
        return pre_head.next;
    }
}

83. Remove Duplicates from Sorted List

解法一：迭代法

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

206. Reverse Linked List

解法一：递归法

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null || head.next==null)return head; //递归结束条件
        
        ListNode n_head=reverseList(head.next); //next为翻转后部分的头部,即原先的尾部
        head.next.next=head;                    //翻转后部分的尾部，本来为null，先将它指向head
        head.next=null;						    //将原先的head.next设为null，防止出现循环链表
        return n_head;                          //返回新的头部
    }
}

解法二：迭代法

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev=null;          //prev初始为null,所以不必担心出现循环链表
        ListNode curr=head;
        while(curr!=null){
            ListNode next=curr.next; //保存curr.next
            curr.next=prev;          //翻转
            prev=curr;
            curr=next;               //prev,curr向前移动一格
        }
        return prev;
    }
}

160. Intersection of Two Linked Lists

解法一：HashSet

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set=new HashSet<ListNode>();
        ListNode curr_a=headA;
        ListNode curr_b=headB;
        while(curr_a!=null){ //遍历链表A，将所有节点加入HashSet
            set.add(curr_a);
            curr_a=curr_a.next;
        }
        while(curr_b!=null){ //遍历链表B，看是否有节点在HashSet存在
            if(set.contains(curr_b))return curr_b;
            curr_b=curr_b.next;
        }
        return null;
    }
}

解法二：双指针

参考官方题解3：十分巧妙

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curr_a=headA;
        ListNode curr_b=headB;
        while(curr_a!=null && curr_b!=null){
            if(curr_a==curr_b)return curr_a; //交点
            curr_a=curr_a.next;
            curr_b=curr_b.next;
            if(curr_a==null && curr_b==null)return null;//到达终点，证明不存在
            if(curr_a==null)curr_a=headB; //a接入b链
            if(curr_b==null)curr_b=headA; //b接入a链
        }
        return null;
    }
}

234. Palindrome Linked List

解法一：栈

• 简明，和数组的做法没有区别，但是空间复杂度O(n)

class Solution {
    public boolean isPalindrome(ListNode head) {
        Stack<Integer> stack=new Stack<Integer>(); //空间复杂度O(n)
        ListNode curr=head;
        while(curr!=null){ //第一次遍历，将所有值压入栈内
            stack.push(curr.val);
            curr=curr.next;
        }
        while(head!=null){ //第二次遍历，逐一比对
            if(stack.pop()!=head.val)return false;
            head=head.next;
        }
        
        return true;
    }
}