数据结构之链表练习题(leetCode)

1.移除链表元素(203)

题目: 给你一个链表的头节点 head 和一个整数val,请你删除链表中所有满足Node.val == val的节点,并返回新的头节点。
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
方法一:这道题是删除链表中所有等于val的元素,需要考虑两种情况。

  1. 头节点是要删除的节点,这时候我们循环判断head的值,但是head不能为空,这样就是链表中没元素了。
  2. 头节点确定不是要删除的结点,我们就遍历链表判断后面的值,因为我们找的是前驱结点,所以我们要保证待删除的结点不能为空,否则会造成空指针异常。造成了pre遍历到最后一个结点,已经没有要判断的结点了。
public ListNode removeElements(ListNode head, int val) {
    while(head != null && head.val == val){
        head = head.next;
    }
    for (ListNode pre = head; pre != null; pre = pre.next) {
        while(pre.next != null && pre.next.val == val) {
            pre.next = pre.next.next;
        }
    }
    return head;
}

方法二:递归
三步骤:首先,判断是否能拆分:这道题可以拆成head.val == val和剩下结点是否有val
其次:拆封后解决思路相同
最后:存在终止条件

  1. 理解函数的语义:传入头结点和待删除的值,函数就能删除所有等于val的元素
  2. 将链表分为头结点和其他结点,因为我们只能知道头结点。
  3. 把除头结点之后的链表的删除工作交给子函数运行,子函数就能把元素删除
  4. 判断头结点是否为需要删除的结点,若是,返回头结点的下一个结点;反之,返回头结点
public ListNode removeElements(ListNode head, int val) {
	//链表内没有元素,终止条件
    if (head == null){
        return null;
    }
    head.next = removeElements(head.next,val);
    //删除操作
    if (head.val == val){
        return head.next;
    }
    return head;
}

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

题目:给定一个已排序的链表的头head, 删除所有重复的元素,使每个元素只出现一次 。返回已排序的链表。
输入:head = [1,1,2]
输出:[1,2]
方法一:

  1. 这道题我们不知道要删除的元素是谁,所以我们需要引入两个指针去比较。
  2. 当pre.val == cur.val,说明pre是第一个重复的元素,所以我们保留这个元素,而cur是要删除的元素,所以pre.next = cur.next,然后让cur向后走,等于走一步删一步。
  3. 当pre.val!=cur.val,说明他们不是要删除的元素,一起向后走。直到cur==null,循环完毕,返回头结点。
public ListNode deleteDuplicates(ListNode head) {
    //当链表为空或者只有一个元素的时候,不可能有重复的元素
    if (head == null || head.next == null){
        return head;
    }
    ListNode pre = head;
    ListNode cur = pre.next;
    while(cur != null){
        if (pre.val != cur.val) {
            pre = pre.next;
            cur = cur.next;
        } else {
            pre.next = cur.next;
            cur = cur.next;
        }
    }
    return head;
}

方法二:递归

  1. 将题目拆封成头结点和之后的结点两部分。
  2. 理解函数语义:一个有序的链表,传入头结点,可以将重复元素删除,只保留一个重复的元素,返回删除后的头结点
  3. 第二个结点之后的删除交给子函数去运行。
  4. 由于我们只知道头结点,所以我们将当前的头结点和返回后的头结点相比较,如果相等,就把当前头结点删了,返回head.next;反之,返回head。
public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    head.next = deleteDuplicates(head.next);
    if (head.val == head.next.val) {
        return head.next;
    }
    return head;
}

在这里插入图片描述

3.删除排序链表中的重复元素 II(82)

题目:给定一个已排序的链表的头head,删除原始链表中所有重复数字的节点,只留下不同的数字。返回已排序的链表 。
输入:head = [1,2,3,3,4,4,5]
输出:[1,2,5]
方法一:

  1. 这里引入了三个指针.如果两个指针的话,当pre指向重复元素的话,就删不掉了。因为重复元素都要删除,所以pre要指向不重复的元素,我们就让剩下两个指针判断结点是否重复。
  2. 当cur.val != next.val,三指针同时向后移动
  3. 当cur.val == next.val,循环让next向后移动,移动到第一个和cur不相等的元素,意味着pre之后next之前的元素都是要删除的元素。所以pre.next = next把元素删除
  4. 删除后cur和next向后移动一个结点。pre不能向后移动,因为有可能cur和next依旧相等。
public ListNode deleteDuplicates(ListNode head) {
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    ListNode pre = dummyHead;
    ListNode cur = pre.next;
    while(cur != null) {
        ListNode next= cur.next;
        if (next == null){
            //链表内只有一个节点或者链表遍历完了
            break;
        } else {
            //链表内至少有两个结点
            //不相等,三指针同时向后移动,在下一次循环开始的时候,next会向后走一步
            if (cur.val != next.val) {
                pre = pre.next;
                cur = cur.next;
            } else {
            	//相等时,让next向后走到第一个不相等的元素
                while(next != null && cur.val == next.val) {
                    next = next.next;
                }
                pre.next = next;
                //cur向后走一步
                cur = next;
            }
        }
    }
    //返回头结点
    return dummyHead.next;
}

图解:
在这里插入图片描述

方法二:递归

  1. 理解语义:传入头结点,这个函数能把所有重复元素都删除,并返回新的头结点。所以我们只要处理头结点就可以了
  2. 如果head.val != head.next.val,证明第一个结点和第二个结点不相等,我们把第二个结点开始交给子函数处理就可以了。
  3. 循环判断head.val是否等于head.next.val,相等的话把头删掉,一直向后走,走第一个与头不相等的结点。循环判断结束后,nextHead一定是不重复的头结点,我们把这个结点作为新的头结点传入交给子函数处理。
public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null){
        return head;
    }
    if (head.val != head.next.val) {
        head.next = deleteDuplicates(head.next);
        return head;
    } else {
    	//删头结点
        ListNode nextHead = head.next;
        while (nextHead != null && head.val == nextHead.val){
            nextHead = nextHead.next;
        }
        return deleteDuplicates(nextHead);
    }
}

4.反转链表(206)

题目:给你单链表的头节点 head,请你反转链表,并返回反转后的链表。
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
方法一:这道题的核心思想就是头插法,在遍历链表的同时,新建节点进行头插到新链表,当遍历完了,就反转了整个链表。

public ListNode reverseList(ListNode head) {
    ListNode dummyHead = new ListNode();
    while(head != null) {
        ListNode node = new ListNode(head.val);
        node.next = dummyHead.next;
        dummyHead.next = node;
        head = head.next;
    }
    return dummyHead.next;
}

方法二:迭代
核心思想:定义三个指针,pre,cur,next。原先的1->2,现在需要2->1,1->null
让pre = null,cur = head,next暂存下一个需要处理的结点,因为没有next我们就找不到下一个节点了,和谈反转呢?
当cur走向null,这时候pre正好是反转后的头结点,返回pre就可以了

public ListNode reverseList(ListNode head) {
    if(head == null || head.next == null) {
        return head;
    }
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

在这里插入图片描述

方法三:递归

  1. 理解语义:传入头结点,我们能将链表反转,并返回新的头结点
  2. 第二个节点开始交给子函数去反转,这道题返回后的头结点newHead是5.然后只要把原先的头结点链接到最后,并让原先头结点指向空就可以了。
  3. 因为要让原先的头结点连到最后,需要暂存一下原链表的第二个结点,也就是反转后的倒数第二个节点。
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null){
        return head;
    }
    ListNode node = head.next;
    ListNode newHead = reverseList(head.next);
    node.next = head;
    //不能省略,会成环
    head.next = null;
    return newHead;
}

图示:在这里插入图片描述

5.链表的中间结点(876)

题目:给定一个头结点为 head 的非空单链表,返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
输入:[1,2,3,4,5,6]
输出:此列表中的结点 4 (序列化形式:[4,5,6])
由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。
方法一:1. 计算链表中结点个数
2. 遍历链表找到中间节点
3. 返回中间节点

public ListNode middleNode(ListNode head) {
    int count = 0;
    for(ListNode x = head; x != null; x = x.next) {
        count ++;
    }
    ListNode x = head;
    for (int i = 0; i < count / 2; i++) {
        x = x.next;
    }
    return x;
}

方法二:快慢指针(双引用)

  1. 引入两个指针,一个走一步,一个走两步,当快的指针指向空或者快的指针的下一个结点指向空。慢的指针正好走到了中间结点。
  2. 核心,两个指针,让一个引用先走或者多走几步
public ListNode middleNode(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    while (fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

推导:

设路程为s,slow的速度为V1,fast的速度为V2,所用时间为t
当V2 = 2V1
S = V2 * t
S/2 = V1 * t //正好是中间的结点

6.链表中倒数第k个节点(剑指 Offer 22)

题目:输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
方法一:遍历链表

public ListNode getKthFromEnd(ListNode head, int k) {
    int count = 0;
    for (ListNode x = head; x != null; x = x.next) {
        count ++;
    }
    ListNode node = head;
    for (int i = 0; i < count - k; i++) {
        node = node.next;
    }
    return node;
}

方法二

  1. 定义两个指针fast和slow,让fast先后k步,然后fast和slow一起向后走,当fast走到空,slow正好在倒数第k个位置
  2. 因为fast和slow的相对距离为k步,当fast走到终点,他们的相对距离还是k步,正好就是倒数第k个位置
public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode fast = head;
    for (int i = 0; i < k ; i++) {
        fast = fast.next;
    }
    ListNode slow = head;
    while(fast != null){
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

7.回文链表

题目:给你一个单链表的头节点head,请你判断该链表是否为回文链表。如果是返回 true ;否则返回 false。
输入:head = [1,2,2,1]
输出:true
方法一:新建一个链表,反转原链表到新链表上。同时遍历原链表和新链表,当他们有一个值不相等时,就不是回文数

public ListNode reverseList(ListNode head) {
    ListNode dummyHead = new ListNode();
    while(head != null) {
        ListNode node = new ListNode(head.val);
        node.next = dummyHead.next;
        dummyHead.next = node;
        head = head.next;
    }
    return dummyHead.next;
}
public boolean isPalindrome(ListNode head) {
    ListNode newLink = reverseList(head);
    while(head != null) {
        if (head.val != newLink.val) {
            return false;
        }
        head = head.next;
        newLink = newLink.next;
    }
    return true;
}

方法二
从中间节点之后的链表反转,与中间节点之前的链表进行对比,如果不一样,返回false,反之,ture。

public ListNode reverse(ListNode head){
    if (head == null || head.next == null){
        return head;
    }
    ListNode node = head.next;
    ListNode newHead = reverse(head.next);
    node.next = head;
    head.next = null;
    return newHead;
}
//找中间结点
public ListNode middleNode(ListNode head){
    ListNode fast = head;
    ListNode slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}
public boolean isPalindrome(ListNode head) {
    ListNode midNode = middleNode(head);
    ListNode resHead = reverse(midNode);
    while(resHead != null){
        if (head.val != resHead.val){
            return false;
        }
        resHead = resHead.next;
        head = head.next;
    }
    return true;
}

8.合并两个有序链表(21)

题目:将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
方法一:拼接链表
核心:尾插

  1. 当list1为空,直接返回list2;当list2为空,直接返回list1.
  2. 当两个链表都不为空,比较两个链表中结点的大小。
  3. 两个链表遍历,取出最小值,拼接到链表的尾部
  4. 拼接完了后,当list1还有剩下的结点,将list1的结点拼接到新链表尾部
  5. 拼接完了后,当list2有剩下的结点,将list2结点拼接到新链表尾部
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null){
        return list2;
    }
    if (list2 == null){
        return list1;
    }
    ListNode dummyHead = new ListNode();
    //新链表的尾结点
    ListNode tail = dummyHead;
    while(list1 != null && list2 != null) {
        if(list1.val <= list2.val) {
            tail.next = list1;
            tail = list1;
            list1 = list1.next;
        } else {
            tail.next = list2;
            tail = list2;
            list2 = list2.next;
        }
    }
    if (list1 == null){
        tail.next = list2;
    }
    if (list2 == null){
        tail.next = list1;
    }
    return dummyHead.next;
}

方法二:递归
边界条件一样

  1. 理解语义:传入两个升序的链表,就能拼接成一个大的升序链表,并返回拼接后的头结点。
  2. 这里我们只知道两个链表的头结点,所以我们只要比较这两个头结点的大小。
  3. 如果head1 <= head2,说明head1一定是拼接后链表的头结点,因为是最小的一个。从list1第二个节点开始和整个list2交给子函数处理,他能返回拼接后的头结点。
  4. 我们找出的最小结点的下一个节点就是子函数处理完之后的头结点,所以两个一拼接,就完成了这道题。
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null){
        return  list2;
    }
    if (list2 == null){
        return list1;
    }
    if (list1.val <= list2.val){
        list1.next = mergeTwoLists(list1.next,list2);
        return list1;
    }else {
        list2.next = mergeTwoLists(list2.next,list1);
        return list2;
    }

9.分割链表(02.04)

题目:给你一个链表的头节点head和一个特定值x,请你对链表进行分隔,使得所有小于x的节点都出现在大于或等于x的节点之前。
输入:head = [1,4,3,2,5,2], x = 3
输出:[1,2,2,4,3,5]
分析:

  1. 这道题我们可以采用分割 + 拼接的方法
  2. 首先,创建两个链表,一个链表存放小于x的值;一个链表存放大于x的值。最后将大链表拼接到小链表之后就可以了。
  3. 注意,拆封完了之后大链表还会挂在结点,我们将这个大链表的尾结点的下一个结点的指向空就可以了。
public ListNode partition(ListNode head, int x) {
    if (head == null || head.next == null){
        return head;
    }
    ListNode smallHead = new ListNode();
    ListNode smallTail = smallHead;
    ListNode bigHead = new ListNode();
    ListNode bigTail = bigHead;
    while (head != null) {
        if (head.val < x) {
            smallTail.next = head;
            smallTail = head;
        } else {
            bigTail.next = head;
            bigTail = head;
        }
        head = head.next;
    }
    bigTail.next = null;
    smallTail.next = bigHead.next;
    return smallHead.next;
}

10.相交链表(160)

题目:给你两个单链表的头节点headA和headB,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。

在这里插入图片描述

分析

  1. 当两个链表有相交结点的时候,让两个引用l1,l2分别从前向后走,当l1走到空时,让l1从headB开始走;当l2走到空时,让l2从headA开始走。这样之后,便会找到相交的结点。
  2. 当两个结点不相交的时候,l1走完走headB链表;l2走完走headA链表,当两个链表都走向空的时候,意味着两个链表没有相交结点
  3. 智力题,我人看傻了
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode l1 = headA;
    ListNode l2 = headB;
    while (l1 != l2) {
        l1 = l1 == null ? headB : l1.next;
        l2 = l2 == null ? headA : l2.next;
    }
    return l1;
}

图解:在这里插入图片描述

11.环形链表(141)

题目:给你一个链表的头节点head,判断链表中是否有环。
在这里插入图片描述

解析

  1. 这道题我们可以比喻为环形操场跑步,两个人在跑步,若一个人的速度比另一个快,不管跑了多少圈,一定会“套圈”,追上慢的那个人。
    快慢指针,快的走两步,慢的走一步,当快的追上了慢的,就意味着是个环形链表;当快指针走向空,代表链表没环。
public boolean hasCycle(ListNode head) {
    ListNode fast = head,slow = head;
    while(fast != null && fast.next != null){
        fast = fast.next.next;
        slow = slow.next;
        //追上了
        if (fast == slow){
            return true;
        }
    }
    //直线
    return false;
}

12.反转链表 II(92)

题目:给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回反转后的链表 。
输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]

方法一:三指针 + 头插

public ListNode reverseBetween(ListNode head, int left, int right) {
    ListNode dummyHead = new ListNode();
    dummyHead.next = head;
    //pre指向待反转区间的前驱节点
    ListNode pre = dummyHead;
    //cur指向待反转区间的第一个节点
    ListNode cur = pre.next;
   	//让pre和cur走left - 1步,走到对应位置
    for (int i = 0; i < left - 1; i++) {
        pre = pre.next;
        cur = cur.next;
    }
    //只需要反转right - left次就可以
    for (int i = 0; i < right - left; i++) {
        //暂存下一个要处理的结点
        ListNode next = cur.next;
        //先删除next,在头插到pre的后面
        cur.next = next.next;
        //头插
        next.next = pre.next;
        pre.next = next;
    }
    return dummyHead.next;
}