【无头双向链表和链表练习题2】
文章目录
- 以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
- 输入两个链表，找出它们的第一个公共结点。
- 给定一个链表，判断链表中是否有环
- 无头双向链表的模拟实现
- ArrayList（顺序表）和LinkedList（双向链表）的区别
- 总结
以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前
public class Partition {
public ListNode partition(ListNode pHead, int x) {
// write code here
//创建四个节点
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = pHead;
if(cur == null){
return null;
}
while(cur != null){
if(cur.val < x){
//小于x放左边
if(bs == null){
//当bs里面没有节点时
bs = cur;
be = cur;
}else{
//有节点了用be去遍历
be.next = cur;
be = cur;
}
}else{
//大于x放右边
if(as == null){
//当as里面没有节点时
as = cur;
ae = cur;
}else{
//有节点了用ae去遍历
ae.next = cur;
ae = cur;
}
}
cur = cur.next;
}
//cur遍历完了开始串起来
//如果前面为空
if(bs == null){
return as;
}
//如果都不为空
be.next = as;
//如果后面不为空，要置为空
if(as != null){
ae.next = null;
}
return bs;
}
}
输入两个链表，找出它们的第一个公共结点。
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB){
ListNode cur1 = headA;
ListNode cur2 = headB;
int len1 =0;
int len2 = 0;
//1.求链表的长度
while(cur1 != null){
len1++;//5
cur1 = cur1.next;
}
while(cur2 != null){
len2++;//2
cur2 = cur2.next;
}
cur1 = headA;
cur2 = headB;
//int len = math.abs(len1 - len2);//3
//2.走差值步
if(len1>len2){
for(int i = 0;i < len1-len2;i++){
cur1 = cur1.next;
}
}else{
for(int j = 0;j < len2 - len1;j++){
cur2 = cur2.next;
}
}
//3.同时走
while(cur1 != cur2 ){
cur1 = cur1.next;
cur2 = cur2.next;
}
//如果没相遇，都是空
if(cur1 == null){
return null;
}
return cur1;
}
}
给定一个链表，判断链表中是否有环
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null){
fast = fast.next.next;//走两步
slow = slow.next;//走一步
if(fast == slow){
return true;
}
}
return false;
}
}
无头双向链表的模拟实现
public interface IList {
// 2、无头双向链表实现
//头插法
void addFirst(int data);
void addLast(int data);
//任意位置插入,第一个数据节点为0号下标
void addIndex(int index,int data);
//查找是否包含关键字key是否在单链表当中
boolean contains(int key);
//删除第一次出现关键字为key的节点
void remove(int key);
//删除所有值为key的节点
void removeAllKey(int key);
//得到单链表的长度
int size();
void display();
void clear();
}
public class MyLinkedList implements IList {
//节点内部类
static class ListNode{
public int val;
public ListNode next;
public ListNode prev;
public ListNode(int val){
this.val = val;
}
}
public ListNode head;
public ListNode last;
@Override
public void addFirst(int data) {
//实例化一个节点
ListNode node = new ListNode(data);
if (head == null){
head = node;
last = node;
}else{
node.next = head;
head.prev = node;
head = node;
}
}
//尾插法
@Override
public void addLast(int data) {
ListNode node = new ListNode(data);
if (last == null){
last = node;
head = node;
}else{
last.next = node;
node.prev = last;
last = node;
}
}
//让cur去到index位置
private ListNode findIndex(int index){
ListNode cur = this.head;
//index-1
while(index != 0){
cur = cur.next;
index--;
}
return cur;
}
// 插入节点
@Override
public void addIndex(int index, int data) {
ListNode node = new ListNode(data);
//检查index是否合法
if(index < 0 || index >size()){
//抛出自定义异常
System.out.println("index不合法");
return;
}
//头插法
if(index == 0){
// node.next = head;
// head.prev = node;
// head = node;
addFirst(data);
return;
}
//尾插法
if (index == size()){
// last.next = node;
// node.prev = last;
// last = node;
addLast(data);
return;
}
ListNode cur = findIndex(index);
node.next = cur;
cur.prev.next = node;
node.prev = cur.prev;
cur.prev = node;
}
@Override
public boolean contains(int key) {
ListNode cur = head;
while(cur != null){
if (cur.val == key){
return true;
}
cur = cur.next;
}
return false;
}
@Override
public void remove(int key) {
ListNode cur = head;
while (cur != null) {
//如果等于关键字进入循环
if (cur.val == key) {
//删除头
if (cur == head) {
//如果只有一个节点
head = head.next;//head已经删了
if (head != null){
//如果有很多节点
head.prev = null;
}
last = null;
} else {
//删中间节点和尾巴节点的共同代码
cur.prev.next = cur.next;
if (cur.next == null) {
//删尾巴节点
last = last.prev;
} else {
//删中间节点
cur.next.prev = cur.prev;
}
}
return;
}else{
//不等于，cur往后走
cur = cur.next;
}
}
}
@Override
public void removeAllKey(int key) {
ListNode cur = head;
while (cur != null) {
//如果等于关键字进入循环
if (cur.val == key) {
//删除头
if (cur == head) {
//如果只有一个节点
head = head.next;//head已经删了
if (head != null){
//如果有很多节点
head.prev = null;
}
last = null;
} else {
//删中间节点和尾巴节点的共同代码
cur.prev.next = cur.next;
if (cur.next == null) {
//删尾巴节点
last = last.prev;
} else {
//删中间节点
cur.next.prev = cur.prev;
}
}
}
//继续往后遍历
cur = cur.next;
}
}
//求链表长度
@Override
public int size() {
ListNode cur = head;
int count = 0;
while(cur != null){
count++;
cur = cur.next;
}
return count;
}
//打印链表
@Override
public void display() {
ListNode cur = head;
while(cur != null){
System.out.print(cur.val +" ");
cur = cur.next;
}
System.out.println();
}
@Override
public void clear() {
head = null;
last = null;
}
}
public class TestLink {
//遍历链表
public static void main(String[] args) {
LinkedList<Integer> list =new LinkedList<>();
list.add(1);
list.add(3);
list.add(5);
list.add(7);
list.add(9);
list.add(12);
System.out.println(list);
System.out.println("=================");
for (int i = 0; i < list.size(); i++) {
System.out.print(list.get(i)+" ");
}
}
}
ArrayList（顺序表）和LinkedList（双向链表）的区别
总结
链表的学习就到这里，最重要的就是什么是链表，链表又细分为哪些链表，要会把链表画出来，链表和顺序表的区别，链表的各种方法的实现，链表的各种练习题等。