MylinkedList.java
class ListNode {
public int val;
public ListNode next;
public ListNode(int val) {
this.val = val;
}
}
public class MylinkedList {
//首先需要定义一个链表的头结点 先用穷举法定义一个链表
public ListNode head;
public void createList() {
ListNode listNode1 = new ListNode(12);
ListNode listNode2 = new ListNode(23);
ListNode listNode3 = new ListNode(34);
ListNode listNode4 = new ListNode(45);
ListNode listNode5 = new ListNode(56);
this.head = listNode1;
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
listNode4.next = listNode5;
}
//打印链表的val值
public void display() {
ListNode cur = this.head;
while (cur != null) {
System.out.print(cur.val+ " ");
cur = cur.next;
}
System.out.println();
}
//从指定头节点开始打印
public void display(ListNode newHead) {
ListNode cur = newHead;
while (cur != null) {
System.out.print(cur.val+ " ");
cur = cur.next;
}
System.out.println();
}
//实现链表的大小size()方法
public int size() {
int count = 0;
ListNode cur = this.head;
while (cur != null) {
count++;
cur = cur.next;
}
return count;
}
//判断是否包含关键字key在单链表中，返回boolean值
public boolean contains(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.val == key) {
return true;
}
cur = cur.next;
}
return false;
}
//实现头插法
public void addList(int data) {
ListNode node = new ListNode(data);
node.next = this.head;
head = node;
}
//实现尾插法
public void addLast(int data) {
ListNode node = new ListNode(data);
//如果头结点为null，会有空指针异常，所以要判断头结点是否为null
if (this.head == null) {
this.head = node;
return;
}
ListNode cur = this.head;
while(cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
//实现clear函数
public void clear() {
//粗暴的方法：直接将head头结点置为null
// this.head = null;
//温柔的方法：单链表中一个一个的置为null
while(this.head != null) {
ListNode curNext = this.head.next;
this.head.next = null;
this.head = curNext;
}
}
//删除第一次出现关键字为key的节点
public void remove(int key) {
if (this.head == null) {
System.out.println("单链表为空，不能删除");
return;
}
if (this.head.val == key) {
this.head = this.head.next;
return;
}
ListNode cur = searchPrev(key);
if (cur == null) {
System.out.println("没有你要删除的节点");
return;
}
ListNode del = cur.next;
cur.next = del.next;
}
//找出要删除的前一个节点，返回前一个节点
public ListNode searchPrev(int key) {
ListNode cur = this.head;
while (cur != null) {
if (cur.next.val == key) {
return cur;
}
cur = cur.next;
}
return null;
}
//删除所有值为key的节点
public void removeAllKey(int key) {
if (this.head == null) {
return ;
}
ListNode prev = this.head;
ListNode cur = this.head.next;
while (cur != null) {
if (cur.val == key) {
prev.next = cur.next;
cur = cur.next;
}else {
prev = cur;
cur = cur.next;
}
}
if (this.head.val == key) {
this.head = this.head.next;
}
}
//任意位置插入，第一个数据节点为0号下标
public void addIndex(int index,int data) {
ListNode node = new ListNode(data);
if (index < 0 ||index > size()) {
System.out.println("index下标不合法");
return;
}
if (index == 0) {
addList(data);
return;
}
if (index == size()) {
addLast(data);
return;
}
ListNode cur = findIndex(index);
node.next = cur.next;
cur.next = node;
}
public ListNode findIndex(int index) {
ListNode cur = this.head;
while (index-1 != 0) {
cur = cur.next;
index--;
}
return cur;
}
//反转一个单链表 老师写的方法
public ListNode reverseList () {
if (this.head == null) {
return null;
}
ListNode cur = this.head;
ListNode prev = null;
ListNode curNext;
while(cur != null) {
curNext = cur.next;
cur.next = prev;
prev = cur;
cur = curNext;
}
this.head = prev;
return prev;
}
//反转一个单链表 我写出来的方法
public ListNode reverseList2 () {
if (this.head == null) {return null;}
ListNode cur = this.head;
ListNode curNext = cur.next;
ListNode tmp;
while (curNext != null) {
tmp = curNext.next;
curNext.next = cur;
cur = curNext;
curNext = tmp;
}
this.head.next = null;
this.head = cur;
return head;
}
//给定一个带有头结点head的非空单链表，返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。
//使用快慢指针，路程不一样。当fast为slow的两倍速时，fast结束，slow就在中间路程。
public ListNode middleNode(ListNode head) {
if (this.head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) { //先判断fast是否为空，然后再判断fast.next是否为空
fast = fast.next.next; //不然，如果fast为空，fast.next就会空指针异常
slow = slow.next;
}
return slow;
}
// 输入一个链表，输出该链表中倒数第k个节点
public ListNode func4 (int k) {
// if (k <= 0 || k > size()) {
if (k <= 0 || head == null) {
System.out.println("k值超过范围，不合法！");
return null;
}
ListNode fast = this.head;
ListNode slow = this.head;
while (k-1 != 0) {
fast = fast.next;
if (fast == null) {
System.out.println("k值超过范围，不合法！");
return null;
}
k--;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
//在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针
public ListNode func7() {
//设置一个傀儡节点newHead，让tmp指向newHead，然后将重复的和不重复的分类
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
ListNode cur = this.head;
while (cur != null) {
//保证cur.next也不为null
if (cur.next != null && cur.val == cur.next.val) {
//while是单独的循环，需要重新控制限制条件
while (cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
cur = cur.next;
}else {
tmp.next = cur;
tmp = tmp.next;
cur = cur.next;
}
}
//防止最后一个也是重复的，被删掉。所以，也要判断一下，手动置为null
tmp.next = null;
return newHead.next;
}
}
TestDemo.java
public class TestDemo {
//将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
public static ListNode func5 (ListNode headA, ListNode headB) {
ListNode newHead = new ListNode(-1);
ListNode tmp = newHead;
while(headA != null && headB !=null) {
if (headA.val < headB.val) {
tmp.next = headA;
headA = headA.next;
tmp = tmp.next;
}else {
tmp.next = headB;
headB = headB.next;
tmp = tmp.next;
}
}
if (headA != null) {
tmp.next = headA;
}
if (headB != null) {
tmp.next = headB;
}
return newHead.next;
}
//编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前,最后返回新链表的头结点。
public static ListNode func6(ListNode head,int x) {
//设置四个引用对象，分别代表小于x的链表的前后节点，和大于等于x的链表的前后节点，然后再相连。
ListNode bs = null;
ListNode be = null;
ListNode as = null;
ListNode ae = null;
ListNode cur = head;
while (cur != null) {
if (cur.val < x) {
if (be == null) {
bs = cur;
be = cur;
}else {
be.next = cur;
be = be.next;
}
}else {
if (ae == null) {
ae = cur;
as = cur;
}else {
ae.next = cur;
ae = ae.next;
}
}
cur = cur.next;
}
//有可能没有小于x的值，如果没有小于x得值，be.next就会报空指针异常错误，所以要判断一下。（没有大于x的值的情况包括在里面了）
if (be == null) {
return as;
}
//防止最后一位节点的next不为null
// （当最后一个节点小于x的时候，将其放在前面，后面如果有大于x的节点的值，最后一个节点的next不为null）
// 就需要手动将最后一位置为null
if(ae != null && ae.next != null) {
ae.next = null;
}
be.next = as;
return bs;
}
//第8道题 判断是不是回文
public static boolean func8(ListNode head) {
//第一步：找中间节点（定义一个快慢指针）
if (head == null) {
return true;
}
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next !=null) {
fast = fast.next.next;
slow = slow.next;
}
//此时，中间节点为slow。第二步逆置
ListNode cur = slow.next;
ListNode curNext = cur.next;
while (cur != null) {
curNext = cur.next;
cur.next = slow;
slow = cur;
cur = curNext;
}
//第三步：
while (head != slow) {
if (head.val != slow.val) {
return false;
}
if (head.next == slow) {
return true;
}
head = head.next;
slow = slow.next;
}
return true; //相遇了就return true
}
//第9道题 输入两个链表，找出它们的第一个公共结点。
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) {
return null;
}
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
while (pl != null) {
lenA++;
pl = pl.next;
}
//pl==null
pl = headA;
while (ps != null) {
lenB++;
ps = ps.next;
}
//ps==null
ps = headB;
int len = lenA-lenB;//差值步
if(len < 0) {
pl = headB;
ps = headA;
len = lenB-lenA;
}
//1、pl永远指向了最长的链表 ps 永远指向了最短的链表 2、求到了差值len步
while (len != 0) {
pl = pl.next;
len--;
}
while (pl != ps ) {
pl = pl.next;
ps = ps.next;
}
return pl;
}
// pl走差值len步
// 同时走 直到相遇
//第十题：给定一个链表，判断链表中是否有环。
public static boolean func10(ListNode head) {
if (head == null) {
return false;
}
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;
}
//第十一题：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null
public static ListNode func11(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;
}
// return true;
//方法走到这一行，说明单链表有环。
ListNode cur = head;
while (fast != cur) {
fast = fast.next;
cur = cur.next;
}
return fast;
}
//把没环的单链表编程有换的单链表
public static void hasCircle(ListNode head) {
ListNode cur = head;
while(cur.next != null) {
cur = cur.next;
}
cur.next = head.next.next;
}
//将两个链表变成Y相交的链表
public static void intersection(ListNode headA,ListNode headB) {
ListNode cur = headB;
while (cur.next != null) {
cur = cur.next;
}
cur.next = headA.next.next.next;
}
//用递归实现删除所有值为key的节点
public static ListNode removeAllKey2(ListNode head,int key) {
if(head == null){
return null;
}
//递归调用
ListNode res = removeAllKey2(head.next,key);
if(head.val == key){
return res;
}else {
head.next = res;
return head;
}
}
//用递归实现反转单链表
public static ListNode reverseList2(ListNode head) {
if (head == null ||head.next == null) {
return head;
}
ListNode ret = reverseList2(head.next);
head.next.next = head;
head.next = null;
return ret;
}
public static void main(String[] args) {
MylinkedList mylinkedList = new MylinkedList();
MylinkedList mylinkedList1 = new MylinkedList();
mylinkedList1.addLast(11);
mylinkedList1.addLast(27);
// mylinkedList1.display();
// mylinkedList.createList();
mylinkedList.addLast(1);
mylinkedList.addLast(2);
mylinkedList.addLast(3);
mylinkedList.addLast(4);
mylinkedList.addLast(5);
mylinkedList.display();
// TestDemo.intersection(mylinkedList.head, mylinkedList1.head);
// mylinkedList.head = TestDemo.removeAllKey2(mylinkedList.head,23);
// mylinkedList.head = TestDemo.reverseList2(mylinkedList.head);
mylinkedList.display(TestDemo.reverseList2(mylinkedList.head));
// ListNode node = TestDemo.getIntersectionNode(mylinkedList.head, mylinkedList1.head);
// System.out.println(node.val);
// System.out.println(TestDemo.func10(mylinkedList.head));
// TestDemo.hasCircle(mylinkedList.head);
// System.out.println(TestDemo.func10(mylinkedList.head));
// ListNode node = TestDemo.func11(mylinkedList.head);
// System.out.println(node.val);
// ListNode ret = TestDemo.func5(mylinkedList.head,mylinkedList1.head);
// boolean flg = TestDemo.func8(mylinkedList.head);
// System.out.println(flg);
// ListNode ret = TestDemo.func6(mylinkedList.head,29);
// System.out.println(mylinkedList.func4(2).val);
// mylinkedList.func7();
// mylinkedList.display(ret);
// ListNode ret = mylinkedList.func4(7);
// ListNode ret = mylinkedList.middleNode(mylinkedList.head);
// System.out.println(ret.val);
// ListNode ret = mylinkedList.reverseList();
// ListNode ret1 = mylinkedList.reverseList2();
// mylinkedList.display(ret1);
// mylinkedList.remove(56);
// mylinkedList.display();
// mylinkedList.removeAllKey(23);
// mylinkedList.display();
// mylinkedList.clear();
// mylinkedList.addIndex(1,400);
// mylinkedList.display();
// System.out.println(mylinkedList.size());
// System.out.println(mylinkedList.contains(56));
}
}
