【数据结构练习题】链表与LinkedList

顺序表与链表LinkedList

选择题
链表面试题
- 1. 删除链表中等于给定值 val 的所有节点。
- 2. 反转一个单链表。
- 3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
- 4. 输入一个链表，输出该链表中倒数第k个结点。
- 5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
- 6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。
- 7. 链表的回文结构。
- 8. 输入两个链表，找出它们的第一个公共结点。
- 9. 给定一个链表，判断链表中是否有环。
- 10. 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 NULL
- 11. 删除链表中重复的结点

选择题

1
在这里插入图片描述 A错误：头插不需要遍历链表，与链表长度无关
B错误：尾插不需要遍历链表，因为有一个引用指向了尾结点，可以直接插入
C错误：删除第一个节点也不需要遍历链表
D正确：删除最后一个节点之前，先要把倒数第二个节点找到，因为最后一个节点删除之后，需要将倒数第二个节点的next置为null 故需要遍历链表
因此选择D
2
在这里插入图片描述
答案：D
解析：二叉树属于树形结构，不是线性的，队列，链表，顺序表都属于线性表
3

答案：D
解析：链表的插入和删除不是所有情况下都比顺序表快，比如尾插尾删，顺序表的时间复杂度为O（1），并且如果是单链表，如果要在中间某个节点的前面插入/删除一个节点，则需要遍历。所以时间的快慢要分情况看待。
4
在这里插入图片描述

5

A错误：ArrayList中的元素不一定有序，ArrayList没有要求里面的元素必须有序，可能有序也可能不有序
B正确：ArrayList中的元素可以通过下标修改
C错误：ArrayList中的元素没要求必须要唯一，可以唯一也可以重复
D错误：ArrayList中的元素是通过下标访问的，而不是通过key
故正确应该选B
6
在这里插入图片描述
A正确：ArrayList 和 LinkedList都是实现了List接口
B正确：ArrayList是动态类型顺序表，插入时当空间不足时会自动扩容
C正确：LinkedList底层是链表结构，链表不支持随机访问，如果要访问任意元素只能通过查找处理
D错误：LinkedList中插入或者删除元素，只需要修改几个引用的指向即可，不需要搬移愿意，时间复杂度O(1)。ArrayList任意位置插入和删除时才需要搬移，时间复杂度O(N)

链表面试题

1. 删除链表中等于给定值 val 的所有节点。

OJ链接

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

2. 反转一个单链表。

OJ链接

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
}

3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

OJ链接
在这里插入图片描述

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

4. 输入一个链表，输出该链表中倒数第k个结点。

OJ链接
在这里插入图片描述

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = Integer.parseInt(sc.next());
            ListNode head = new ListNode(-1);
            ListNode temp = head;
          //生成链表
            for (int i = 0; i < n; i++) {
                ListNode node = new ListNode(sc.nextInt());
                temp.next = node;
                temp = temp.next;
            }
            int k = Integer.parseInt(sc.next());
          //使用快慢指针
            if(getKthFromEnd(head.next,k) != null){
                System.out.println(getKthFromEnd(head.next,k).val);
            }
            else{
                System.out.println(0);
            }
             
        }
    }
  	//通过快慢指针搜索
    public static ListNode getKthFromEnd(ListNode head,int k){
        if(k<=0||head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        for(int i=0;i<k-1;i++){
            fast=fast.next;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}
class ListNode{
    ListNode next;
    int val;
    ListNode(int val){
        this.val=val;
        next=null;
    }
}

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

OJ链接
在这里插入图片描述

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead=new ListNode();
        ListNode tmpHead=newHead;
        while(list1!=null&&list2!=null){
            if(list1.val>list2.val){
                tmpHead.next=list2;
                list2=list2.next;
            }else{
                tmpHead.next=list1;
                list1=list1.next;
            }
            tmpHead = tmpHead.next;
        }
        if(list1!=null)
            tmpHead.next=list1;
        if(list2!=null)
            tmpHead.next=list2;
        return newHead.next;
    }
}

6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前。

OJ链接
在这里插入图片描述
有个易错不容易注意到：如果ae.next!=null链表会循环此时应该将ae.next=null

还要设想所有数都会大于x的可能，此时会bs==null 直接return as即可

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;

        ListNode cur=pHead;
        while(cur!=null){
            if(cur.val<x){
                //第一次插入
                if(bs==null){
                    bs=be=cur;
                }else{
                    be.next=cur;
                    be=cur;//或be=be.next;
                }
            }else{
                if(as==null){
                    as=ae=cur;
                }else{
                    ae.next=cur;
                    ae=cur;//或ae=ae.next;
                }
            }
            cur=cur.next;
        }
        //第一个段没有数据
        if(bs==null)
            return as;
        be.next=as;
        //防止最大的数据不是最后一个
        if(ae!=null)
            ae.next=null;
        return bs;
    }
}

7. 链表的回文结构。

OJ链接
在这里插入图片描述
若偶数时则循环到最后head.next==slow即可确定true

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        // write code here
        ListNode slow=head;
        ListNode fast=head;
        //用快慢指针确定链表中点
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;
		
		//翻转后段链表
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        while(head!=slow){
            if(head.val!=slow.val)
                return false;
            if(head.next==slow) //偶数 head和slow不会相遇时
                return true;
            head=head.next;
            slow=slow.next;
        }
        return true;
    }
}

8. 输入两个链表，找出它们的第一个公共结点。

OJ链接
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //分别求2个链表的长度
        ListNode pL=headA;
        ListNode pS=headB;
        int lenA=0;
        int lenB=0;
        while(pL!=null){
            lenA++;
            pL=pL.next;
        }
        while(pS!=null){
            lenB++;
            pS=pS.next;
        }
        pL=headA;
        pS=headB;
        //保证pL指向最长的链表，pS指向最短的链表，len>0
        int len=lenA-lenB;
        if(len<0){
            pL=headB;
            pS=headA;
            len=lenB-lenA;
        }

        //2.让最长的链表先走差值步
        while(len!=0){
            pL=pL.next;
            len--;
        }

        //3.就是相遇的点
        while(pL!=pS){
            pL=pL.next;
            pS=pS.next;
        }
        return pL;
    }
}

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

OJ链接

【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

【扩展问题】

为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
快指针一次走3步，走4步，…n步行吗？

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
         if(head==null)
            return false;//可以不写
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow)
                return true;
        }
        return false;
    }
}

10. 给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 NULL

OJ链接

结论
让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
证明

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null)
            return null;
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
                break;
        }
        if(fast==null||fast.next==null)
            return null;
        fast=head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
}

11. 删除链表中重复的结点

OJ链接在这里插入图片描述
易忽略的点：应将手动将tmpHead.next置空防止后边到最后一个节点都是重复节点

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode cur=pHead;
        ListNode newHead=new ListNode(-1);
        ListNode tmpHead=newHead;
        //遍历每一个节点
        while(cur!=null){
            if(cur.next!=null&&cur.val==cur.next.val){
                //一直让cur走到不重复的节点 
                while(cur.next!=null&&cur.val==cur.next.val){
                    cur=cur.next;
                }                    
                cur=cur.next;
            }else{
                //把这个节点加入到不重复链表中
                tmpHead.next=cur;
                tmpHead=tmpHead.next;
                cur=cur.next;
            }

        }
        //手动将tmpHead.next置空防止后边到最后一个节点都是重复节点 
        tmpHead.next=null;
        return newHead.next;
    }
}