leetcode刷题-链表

简单题

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

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

思路：每次都取两个中较小的一个，直到其中一个遍历到链表结尾结束遍历。如果这个时候还是剩下的元素，肯定比之前的元素都大，直接添加到链表结尾。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null)
        {
            return l2;
        }
        if(l2 ==null)
        {
            return l1;
        }
        ListNode merged =null;
        ListNode head =null;
        while(l1!=null &&l2!=null){
            if(head ==null){
                if(l1.val <l2.val){
                    merged =l1;
                    l1=l1.next;
                    
                }else{
                    merged =l2;
                    l2=l2.next;
                }
                head =merged;
                continue;
            }
            if(l1.val<l2.val){
                merged.next =l1;
                l1 =l1.next;
            }else{
                merged.next =l2;
                l2=l2.next;
            }
            merged =merged.next;
        }
        while(l1 !=null){
            merged.next =l1;
            l1=l1.next;
            merged=merged.next;
        }
        while(l2 !=null){
            merged.next =l2;
            l2=l2.next;
            merged=merged.next;
        }
        return head;
    }
}

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

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

示例 1:

输入: 1->1->2
输出: 1->2

示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

解题思路：如果是重复的，我们更改当前结点的 next 指针，以便它跳过下一个结点并直接指向下一个结点之后的结点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current =head;
        while(current !=null&&current.next !=null ){
            if(current.val==current.next.val){
                current.next=current.next.next;}
            
                else{
                    current=current.next;
                }
}
           return head;    
        }
             
    }

141. 环形链表

给定一个链表，判断链表中是否有环。

hash法

我们遍历所有结点并在哈希表中存储每个结点的引用（或内存地址）。如果当前结点为空结点 null（即已检测到链表尾部的下一个结点），那么我们已经遍历完整个链表，并且该链表不是环形链表。如果当前结点的引用已经存在于哈希表中，那么返回 true（即该链表为环形链表）。

public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<>();
    while (head != null) {
        if (nodesSeen.contains(head)) {
            return true;
        } else {
            nodesSeen.add(head);
        }
        head = head.next;
    }
    return false;
}

双向链表

通过使用具有不同速度的快、慢两个指针遍历链表，空间复杂度可以被降低至O(1)O(1)。慢指针每次移动一步，而快指针每次移动两步。

如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回 false。

//查询是否有环（双向链表）
public boolean hasCycle1(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。

A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

解题思路：如果A和B是两个长度不同的链表，他们相交前的长度一定是不同的，计算链表长度差额n，让长的链表指针先开始移动n，两个指针再一起移动，指针相遇时就是链表结点的相交处

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lengthA=calcListLength(headA);
        int lengthB=calcListLength(headB);
        int lenc=lengthA-lengthB;
     
        
        for(int i=0;i<Math.abs(lenc);i++){
            if(lenc>0)
            {
                headA=headA.next;
            }
            else{
                headB=headB.next;
            }
        }
        while( headA !=null && headB !=null){
            if(headA == headB){
                return headA;
            }
          
            headA=headA.next;
            headB=headB.next;
    
    }   
        return null;
    }
    
    public int calcListLength(ListNode Node){
        ListNode head=Node;
        int i=0;
        while(head !=null){
            head=head.next;
            i++;
        }
        return i;
    }
    
    
    
}

206. 反转链表

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

迭代法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) { //先考虑链表是否为空
            return null;
        }
        ListNode p1 = head;
        ListNode p2 = head.next;
        p1.next = null;
        while (p2 != null) {
            ListNode temp = p2.next;
            //设置一个tmp指针指向后续
            p2.next = p1;
            //p2指针反转
            p1 = p2;
            //p1指针向前进
            p2 = temp;  
            //p2指针向前进
        }
        return p1;
    }
}

递归法

解题思路：
假设1->2->3->4->5->null
已经变成1->2<-3<-4<-5<-null

2是head.next

2的后继是head.next.next

我们希望2的后继指向head所以是head=head.next.next

再去除1->2的环head.next=null

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode subListHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return subListHead;
    }
}

中等题

2. 两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

输出：7 -> 0 -> 8

原因：342 + 465 = 807

非递归解法

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
               ListNode dummyHead = new ListNode(0);
               ListNode p = l1, q = l2, curr = dummyHead;
               int carry = 0;
               while (p != null || q != null) {
                   int x = (p != null) ? p.val : 0;
                   int y = (q != null) ? q.val : 0;
                   int sum = carry + x + y;
                   carry = sum / 10;
                   curr.next = new ListNode(sum % 10);
                   curr = curr.next;
                   if (p != null) p = p.next;
                   if (q != null) q = q.next;
               }
               if (carry > 0) {
                   curr.next = new ListNode(carry);
               }
               return dummyHead.next;
           }

递归写法

class Solution {
 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null || l2 == null) {
        return l1 == null ? l2 : l1;
    }
    int value = l1.val + l2.val;
    ListNode result = new ListNode(value % 10);
    //节点相加
    result.next = addTwoNumbers(l1.next, l2.next);
    //节点相加的结果和余数相加.
    if (value >= 10) {
        result.next = addTwoNumbers(new ListNode(value / 10),
                      result.next);
    }
    return result;
}
}

基础回顾

ListNode的类结构

public class ListNode
{
    int val;//定义val变量值，存储节点值
    ListNode next;//定义next指针，指向下一个节点，维持节点连接
    
    public ListNode(int x){
        val=x;
    }

注意注意val只代表当前指针的值，比如p->val表示p指针的指向的值；而p->next表示链表下一个节点，也是一个指针。
构造函数包含两个参数 _value 和 _next ，分别用来给节点赋值和指定下一节点