阅读量:3
目录
1.扑克牌游戏
public class Card { private String suit; private int rank; public Card( int rank,String suit) { this.suit = suit; this.rank = rank; } @Override public String toString() { return"{"+suit+rank+"} "; } } import java.util.ArrayList; import java.util.List; import java.util.Random; public class CardDemo { public static final String[] stuits={"♠","方块","♥","♣"}; public List<Card> buyCard() { List<Card> cardList = new ArrayList<>(); for (int i = 0; i < 13; i++) { for (int j = 0; j < 4; j++) { int rank = i; String suit = stuits[j]; Card card = new Card(rank,suit); cardList.add(card); } } return cardList; } public void shuffle(List<Card> cardList){ Random random = new Random(); for (int i =cardList.size()-1; i > 0; i--) { int index = random.nextInt(i); swap(cardList,i,index); } } private void swap (List<Card>cardList,int i,int j){ Card tmp = cardList.get(i); cardList.set(i,cardList.get(j)); cardList.set(j,tmp); } public List<List<Card>> play(List<Card>cardList){ List<Card> hand0 = new ArrayList<>(); List<Card> hand1 = new ArrayList<>(); List<Card> hand2 = new ArrayList<>(); List<List<Card>> hand = new ArrayList<>(); hand.add(hand0); hand.add(hand1); hand.add(hand2); for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { Card card = cardList.remove(0); hand.get(j).add(card); } } return hand; } } import java.util.List; public class Test { public static void main(String[] args) { //买牌 CardDemo cardDemo = new CardDemo(); List<Card> cardList = cardDemo.buyCard(); System.out.println(cardList); //洗牌 cardDemo.shuffle(cardList); //轮流发牌 List <List<Card>> ret = cardDemo.play(cardList); for (int i = 0; i < ret.size(); i++) { System.out.println("第"+(i+1)+"个人的牌"+ret.get(i)); } } } 2.链表基本功能的实现（单项链表）
public class Test { public static void main(String[] args) { MySingleList list = new MySingleList(); list.CreatList(); list.clear(); list.display(); } } public class MySingleList implements IList { static class ListNode{ private int val; private ListNode next; public ListNode(int val){ this.val = val; } } public ListNode head; public void CreatList(){ ListNode node1 = new ListNode(12); ListNode node2 = new ListNode(12); ListNode node3 = new ListNode(23); ListNode node4 = new ListNode(45); ListNode node5 = new ListNode(56); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; this.head = node1; } @Override public void addFirst(int data) { ListNode node = new ListNode(data); node.next = head; head = node; } @Override public void addLast(int data) { ListNode node = new ListNode(data); ListNode cur = head; if(head == null){ head = node; return; } while(cur.next != null ){ cur = cur.next; } cur.next = node; } @Override public void addIndex(int index, int data) { int len = size(); if(index < 0 || index > len){ System.out.println("index位置不合法"); return; } if( index == 0){ addFirst(data); return; }if(index == len){ addLast(data); return; } ListNode node = new ListNode(data); ListNode cur =head; while(index - 1 != 0){ cur = cur.next; index--; } node.next = cur.next; cur.next = node; } @Override public boolean contains(int key) { ListNode cur = head; while(cur != null){ if(cur.val == key){ return true; }else cur = cur.next; } return false; } @Override public void remove(int key) { if(head == null){ return; } if(head.val == key){ head = head.next; return; } ListNode cur = findNodeOfKey(key); if(cur == null){ return; } cur.next = cur.next.next; } private ListNode findNodeOfKey(int key){ ListNode cur = head; while(cur.next != null){ if(cur.next.val == key){ return cur; } cur = cur.next; } return null; } @Override public void removeAllKey(int key) { if (head == null) { return; } ListNode pre = head; ListNode cur = head.next; while (cur != null) { if (cur.val == key) { pre.next = cur.next; cur = cur.next; } else { pre = cur; cur = cur.next; } } if (head.val == key){ head = head.next; } } @Override public int size() { ListNode cur = this.head; int len = 0; while(cur != null){ len++; cur = cur.next; } System.out.println(); return len; } @Override public void clear() { ListNode cur = head; while(cur != null){ ListNode curN = cur.next; cur.next = null; cur = curN; } head = null; } @Override public void display() { ListNode cur = head; while ((cur != null)){ System.out.print(cur.val+" "); cur = cur.next; } } } public interface IList { public void addFirst(int data); public void addLast(int data); public void addIndex(int index,int data); public boolean contains (int key); public void remove(int key); public void removeAllKey(int key); public int size(); public void clear(); public void display(); }3.移除链表元素力扣
public class Solution { public ListNode removeElements(ListNode head, int val) { if(head == null){ return head; } ListNode pre = head; ListNode cur = head.next; while(cur != null){ if(cur.val == val){ pre.next = cur.next; cur = cur.next; }else{ pre = cur; cur = cur.next; } } if(head.val == val){ head = head.next; } return head; } } 4.反转链表力扣
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode reverseList(ListNode head) { if(head == null){ return head; } ListNode cur = head.next; head.next = null; while(cur != null){ ListNode curN = cur.next; cur.next = head; head = cur; cur = curN; } return head; } }5.链表的中间结点
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode middleNode(ListNode head) { if(head == null){ return head; } ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; } }5.返回倒数第k个节点
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int kthToLast(ListNode head, int k) { if(head == null){ return head.val; } ListNode fast = head; ListNode slow = head; int count = k - 1; while(count != 0){ fast = fast.next; count--; } while(fast.next != null){ fast = fast.next; slow = slow.next; } return slow.val; } }6.合并两个有序链表
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode newHead = new ListNode(-1); ListNode tmp = newHead; while(list1 != null && list2 != null){ if(list1.val <= list2.val){ tmp.next = list1; list1 = list1.next; tmp = tmp.next; }else{ tmp.next = list2; tmp = tmp.next; list2 = list2.next; } } if(list1 != null){ tmp.next = list1; } if(list2 != null){ tmp.next = list2; } return newHead.next; } }7.链表基本功能的实现（双向链表）
public class test { public static MyLinkedList.ListNode mergeTwoLists(MyLinkedList.ListNode list1,MyLinkedList. ListNode list2) { MyLinkedList. ListNode newHead = new MyLinkedList.ListNode(-1); MyLinkedList. ListNode tmp = newHead; while(list1 != null && list2 != null){ if(list1.val < list2.val){ tmp.next = list1; list1 = list1.next; tmp = tmp.next; } else{ tmp.next = list2; tmp = tmp.next; list2 = list2.next; } } if(list1 != null){ tmp.next = list1; } if(list2 != null){ tmp.next = list2; } return newHead.next; } public static void main(String[] args) { MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addLast(1); myLinkedList.addLast(5); myLinkedList.addLast(9); myLinkedList.addLast(21); myLinkedList.addLast(7); myLinkedList.addLast(21); MyLinkedList myLinkedList1 =new MyLinkedList(); myLinkedList1.addLast(1); myLinkedList1.addLast(5); myLinkedList1.addLast(9); myLinkedList1.addLast(21); myLinkedList1.addLast(7); myLinkedList1.addLast(21); MyLinkedList.ListNode newHead = mergeTwoLists( myLinkedList.head,myLinkedList1.head); myLinkedList.display2(newHead); } }public class MyLinkedList implements IList{ static class ListNode { public int val; public ListNode preV; public ListNode next; public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last; @Override public void addFirst(int data) { ListNode cur = head; ListNode node = new ListNode(data); if(head.next == null){ head = last = node; }else{ node.next = cur; cur.preV = node; head = node; } } @Override public void addLast(int data) { ListNode cur = head; ListNode node = new ListNode(data); if(head == null) { head = last = node; }else{ last.next = node; node.preV = last; last = node; } } @Override //在指点位置增删元素 public void addIndex(int index, int data) { int len = size(); if(index < 0 || index > len ){ System.out.println("不符合条件"); return; }if(index == 0){ addFirst(index); return; }if(index == len){ addLast(data); return; }else{ ListNode cur = findOfKey(index); ListNode node = new ListNode(data); node.next = cur; node.preV = cur.preV; cur.preV.next = node; cur.preV = node; } } private ListNode findOfKey(int index){ ListNode cur = head; while(index != 0){ cur = cur.next; index--; } return cur; } @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; if (head != null) { head.preV = 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 void removeAllKey(int key) { ListNode cur = head; while(cur != null) { if (cur.val == key) { if (cur == head) { head = head.next; if (head != null) { head.preV = null; } } else { cur.preV.next = cur.next; if (cur.next == null) { last = last.preV; } cur.next.preV = cur.preV; } } cur = cur.next; } } @Override public int size() { ListNode cur = head; int len = 0; while(cur != null){ len++; cur = cur.next; } return len; } @Override public void clear() { ListNode cur = head; if(cur != null){ ListNode curN = cur.next; cur.preV = null; cur.next = null; cur = curN; } head = null; last = null; } @Override public void display() { ListNode cur = head; while(cur != null){ System.out.print(cur.val+" "); cur = cur.next; } System.out.println(); } //在指定位置进行打印 public void display2(ListNode newHead) { ListNode cur = head; while (cur != null) { System.out.print(cur.val + " "); cur = cur.next; } System.out.println(); } public ListNode reverseList() { if(head == null){ return head; } ListNode cur = head.next; head.next = null; while(cur != null){ ListNode curN = cur.next; cur.next = head; head = cur; cur = curN; } return head; } }public interface IList { public void addFirst(int data); public void addLast(int data); public void addIndex(int index,int data); public boolean contains (int key); public void remove(int key); public void removeAllKey(int key); public int size(); public void clear(); public void display(); } 8.链表分割
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 as = null; ListNode ae = null; ListNode bs = null; ListNode be = null; ListNode cur = pHead; while(cur != null){ if(cur.val < x){ if(as == null){ as = ae = cur; }else{ ae.next = cur; ae = ae.next; } }else{ if(bs == null){ bs = be =cur; }else{ be.next = cur; be = be.next; } } cur = cur.next; } if(as == null){ return bs; } ae.next = bs; if(bs != null){ be.next = null; } return as; } } 