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

选择题

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 hereListNode 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>0int 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;}
}