链表:当我踏上算法之路,我发现...

2020.09.30 09:09:53
14
阅读约 3 分钟

链表 #

反转链表 #

一杯茶,一包烟,一道链表做一天

题干:
反转一个单链表。
例子:

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

解析:

迭代解法:

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

回文链表 #

题干:传送门
请判断一个链表是否为回文链表。

例子1:

输入: 1->2
输出: false

例子2:

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

思路:使用快慢指针,快指针到尾部之后,满指针正好处于中间位置,翻转前半部分与后面的值对比。

环形链表 #

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

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

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

示例:
img

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

解法:快慢指针,当快指针追上满指针时,即可判断出有循环。

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; //能跳出循环走到这一步就说明,存在slow==fast,也就是存在环形了
    }
}

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

题干:
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
例子:

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

思路:添加一个当前节点的指针,判断当前节点与下一个节点值是否一样,如果相等,则将当前节点的指针指向next.next,否则,将指针移动到下一节点。
循环条件:当前节点不为null并且下一节点也不为null
解答:

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

两数相加 #

题干:
给出两个非空的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

解答:

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        getNumber(l1,l2,0);
        return l1;
    }
    
    (begin)
    private void getNumber(ListNode l1, ListNode l2, int carry ) {
        if(l1==null && l2 ==null)  return;

         carry +=  (l1!=null?l1.val:0)+ (l2!=null?l2.val:0);
         // 余数加到尾部
         l1.val = carry%10;
         // 逢10进1 
         carry/=10;
        
        // 补齐两个链表的空余,使两个链表的长度始终保持一致
        if(l2.next==null && l1.next !=null) l2.next=new ListNode(0);
        if(l1.next==null && l2.next !=null) l1.next=new ListNode(0);
        if(l1.next==null && carry>0 ) {
            l1.next = new ListNode(0);
             l2.next = new ListNode(0);
        }
       getNumber(l1.next,l2.next,carry);
       
      (/end) 
    }
}
阅读:14 . 字数:750 发布于 2 个月前
Copyright 2018-2020 Siques