以给定值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（双向链表）的区别
总结
链表的学习就到这里，最重要的就是什么是链表，链表又细分为哪些链表，要会把链表画出来，链表和顺序表的区别，链表的各种方法的实现，链表的各种练习题等。
