移除链表元素

要求

给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回新的头节点。

示例

输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]

输入:head = [], val = 1
输出:[]

输入:head = [7,7,7,7], val = 7
输出:[]

解答Ⅰ

使用迭代法,在head之前加入dummyhead,让它指向head,因为head可能会被删除,设置cur指针指向当前节点,初始位置为dummyhead,判断如果下一个节点的值等于val,则跳过下一个节点,否则指向当前的cur指针右移一格指向下一个节点;进行遍历删除操作,最后返回dummyhead.next,即为删除操作后的头节点。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyhead = new ListNode(0);
        dummyhead.next = head;
        ListNode cur = dummyhead;
        while(cur.next!=null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return dummyhead.next;
    }
}

解答Ⅱ

链表的定义具有递归的性质,因此链表题目常可以用递归的方法求解。这道题要求删除链表中所有节点值等于特定值的节点,可以用递归实现。

对于给定的链表,首先对除了头节点 head 以外的节点进行判断删除操作,然后判断 head 的节点值是否等于给定的 val。如果head的节点值等于val,则head 需要被删除,因此删除操作后的头节点为head.next;如果head 的节点值不等于 val,则head 保留,因此删除操作后的头节点还是head。上述过程是一个递归的过程。

递归的终止条件是head 为空,此时直接返回head。当head 不为空时,递归地进行删除操作,然后判断head 的节点值是否等于 val 并决定是否要删除head

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        head.next = removeElements(head.next, val);
        return head.val == val ? head.next : head;
    }
}

合并两个有序链表

要求

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

示例

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]

输入:l1 = [], l2 = []
输出:[]

输入:l1 = [], l2 = [0]
输出:[0]

解答Ⅰ

暴力解法,使用迭代法,首先设定一个哨兵节点 dummyhead ,这可以在最后让我们比较容易地返回合并后的链表;让cur指向这个哨兵节点,然后进入循环判断两列中谁的头节点的值更小,l1小则当前节点下一个设为l1l1指向下一个节点;否则l2同样操作;在每轮if判断之后,cur指针也得右移,指向cur.next;当一列整完了,就退出循环,如果l1空了则直接让cur接上l2,否则直接接上l1

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyhead = new ListNode(-1);
        ListNode cur = dummyhead;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
                cur.next=l1;
                l1 = l1.next;
            }else{
                cur.next=l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
    cur.next = l1 == null?l2:l1;
    return dummyhead.next;
    }
}

解答Ⅱ

递归法实现,大体思路都差不多

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(l1,l2.next);
            return l2;
        }
    }
}

环形链表

要求

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

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0开始)。 如果 pos-1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

如果链表中存在环,则返回 true 。 否则,返回 false

示例

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

解答

我也是很亦或,并没找到参数pos,按照没有pos的来,用HashSet来存储遍历的数字,直到Set加不进去为止,说明可以成环,返回true,否则循环结束后返回错误。

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

有趣的龟兔赛跑法,龟(慢指针初始在head),兔(快指针初始在head.next);本应该龟永远追不上兔子,如果跑着跑着,兔子反而得追者乌龟跑,说明肯定有环。

public class Solution {
    public boolean hasCycle(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;
    }
}