顺序表相关OJ：
第1题：
打扑克牌。实现买扑克牌、洗牌和发牌操作。
题解：
class Card{ public int rank;//牌的值 public String suit;//花色 public Card(int rank, String suit) { this.rank = rank; this.suit = suit; } @Override public String toString() { return " "+suit+" "+rank; } } public class CardDemo { public static final String[] suits = {"♣","♥","♦","♠"}; //买牌 public List<Card> buyCard(){ List<Card> Cards = new ArrayList<>(); for (int i = 1; i <= 13; i++) { for (int j = 0; j < 4; j++) { Card card = new Card(i,suits[j]); Cards.add(card); } } return Cards; } //洗牌 public void shuffle(List<Card> Cards){ Random random = new Random(); //这里一定要是ards.size()-1 for (int i = Cards.size()-1; i > 0 ; i--) { int index = random.nextInt(i); swap(Cards,index,i); } } private void swap(List<Card> Cards,int i,int j){ // int tmp = Cards[i]; Card tmp = Cards.get(i); // Cards[i] = Cards[j]; Cards.set(i,Cards.get(j)); // Cards[j] = tmp; Cards.set(j,tmp); } //发牌 public List<List<Card>> play(List<Card> Cards){ List<Card> player1 = new ArrayList<>(); List<Card> player2 = new ArrayList<>(); List<Card> player3 = new ArrayList<>(); List<List<Card>> player = new ArrayList<>(); player.add(player1); player.add(player2); player.add(player3); for (int i = 0; i < 5; i++) { for (int j = 0; j < 3; j++) { Card card = Cards.remove(0); player.get(j).add(card); } } return player; } public static void main(String[] args) { CardDemo cardDemo = new CardDemo(); List<Card> list = cardDemo.buyCard(); System.out.println(list); cardDemo.shuffle(list); System.out.println(list); List<List<Card>> ret = cardDemo.play(list); for (int i = 0; i < ret.size(); i++) { System.out.println("第"+(i+1)+"个人的牌"+ret.get(i)); } } }
代码剖析：
- 使用swap（）；交换方法的时候要注意Cards不是数组，要使用顺序表的操作。
- player.get(j).add(card)；通过player.get(j)就可以知道是哪个玩家抓牌，再将抓到的牌放到自己的手中（就是顺序表中）。
- 有3个玩家，每个玩家的牌是一个ArrayList，再将这些牌看成是另外一个大的顺序表的元素，这个大的顺序表存放的每个元素是一个顺序表，而这个顺序表呢里面存储的是牌！
第2题：
杨辉三角。给定一个非负整数 numRows，生成「杨辉三角」的前 numRows行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
题解：
public List<List<Integer>> generate(int numRows){ List<List<Integer>> ret = new ArrayList<>(); List<Integer> list = new ArrayList<>(); list.add(1); ret.add(list); for (int i = 1; i < numRows; i++) { List<Integer> row = new ArrayList<>(); row.add(1); List<Integer> prev = ret.get(i-1); for (int j = 1; j < i; j++) { int num = prev.get(j)+prev.get(j-1); row.add(num); } row.add(1); ret.add(row); } return ret; }
代码剖析：
- 首先需要一个大的顺序表来存储杨辉三角每一行的顺序表，这每一行的顺序表又存储着各自行的元素比如：1、4、6、4、1。
- 第i行的元素第j个元素就是第i-1行的第j-1元素和j元素的相加的和。
(以下共11道链表题)
链表相关OJ：
第3题：
删除第一次出现的key的值。
题解：
//删除第一次出现的元素key public void remove(int key){ if(head.val == key){ head = head.next; return; } ListNode cur = head; //循环中时cur.next，如果是cur的话会空指针异常 while(cur.next != null){ //这里处理不了头节点 if(cur.next.val == key){ cur.next = cur.next.next; return; } cur = cur.next; } }
代码剖析：
- 一定不能忘记处理头节点
第4题：
删除链表中所有是key的值。
题解：
//删除所有值为key的元素。只遍历了一遍！！ /*public void removeAll(int key){ if(head ==null) return; ListNode cur = head; //会报空指针异常的错误 while(cur.next != null){ if(cur.next.val == key){ cur.next = cur.next.next; } cur = cur.next; } if(head.val == key){ head = head.next; } }*/ public void removeAll(int key){ if(head == null){ return; } ListNode cur = head; ListNode prev = head; while(cur != null){ if(cur.val == key){ prev.next = cur.next; cur = cur.next; }else{ prev = cur; cur = cur.next; } } if(head.val == key){ head = head.next; } }
代码剖析：
- 上面有俩种做法，尽管第一种做法没有用到第3个变量，但是不能有效执行，是一个错误示范。
- 第二种做法是正确写法，头节点的处理一定要放到代码最后来执行，否则若有连续的相同数字在链表最前面的话，不能执行成功，例如：6、6、8、5、4删除6，如果将头节点问题放到前面，则执行结果为6、8、5、4。放到代码最后，执行结果就正常：8、5、4。
第5题：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
题解：
//反转一个单链表 public ListNode reverseList(){ if(head == null) return null; if(head.next == null) return head; //这一步在前，执行完才能把head.next置为null ListNode cur = head.next; head.next = null; while(cur != null){ ListNode curNext = cur.next; cur.next = head; head = cur; cur = curNext; } return head; }
第6题：
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
题解：
//找中间节点只遍历一次 public ListNode middle(){ if(head == null) return null; if(head.next == null) return head; //这里用到了快慢指针 ListNode fast = head; ListNode slow = head; //这里的判断顺序不能颠倒，一定要是 && while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; } return slow; }
代码剖析：
- 本题使用快慢指针
第7题：
输入一个链表，输出该链表中倒数第k个结点。
题解：
//找倒数第k个下标的节点 /*public ListNode FindKthToTail(int k){ if(head == null) return null; checkK(k); ListNode fast = head; ListNode slow = head; //如果让快的先走k步的话，后面的代码会空指针异常 while(k != 0){ fast = fast.next; k--; } while(fast != null){ fast = fast.next; slow = slow.next; } return slow; }*/ public ListNode FindKthToTail(int k){ if(head == null || k <= 0) return null; ListNode fast = head; ListNode slow = head; while(k-1 != 0){ fast = fast.next; if(fast == null){ return null; } k--; } while(fast.next != null){ fast = fast.next; slow = slow.next; } return slow; }
代码剖析：
- 先让fast走k-1步，再让fast和slow一起走，当fast.next==null时，slow所指向的就是倒数第k个节点。
第8题：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
题解：
// 合并俩个有序链表，合并成一个有序链表 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; list2 = list2.next; tmp = tmp.next; } } if(list1 != null){ tmp.next = list1; } if(list2 != null){ tmp.next = list2; } //返回的是newHead.next，不能返回newHead return newHead.next; }
第9题：
现有一链表，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
题解：
//以x为基准，大于x的在后，小于x的在前 public ListNode partition(int x){ ListNode bs = null; ListNode be = null; ListNode as = null; ListNode ae = null; ListNode cur = head; while(cur != null){ if(cur.val < x){ if(bs == null){ bs = cur; be = cur; }else{ be.next = cur; be = be.next; } }else{ if(as == null){ as = cur; ae= cur; }else{ ae.next = cur; ae = ae.next; } } cur = cur.next; } //判断bs是不是空，如果是空说明前端不存在元素 if(bs == null){ return as; } //将前端和后端联系起来 be.next = as; if(as != null){ //将最后一个元素置为空 ae.next = null; } return bs; }
代码剖析：
- 重点判断bs能不能为空，ae必须置为空，如果不置为空有可能发生死循环。
第10题：
对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
题解：
//链表的回文结构 public boolean chkPalindrome(){ if(head == null) return true; //找到中间位置 ListNode fast = head; ListNode slow = 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){ return true; } head = head.next; slow = slow.next; } return true; }
第11题：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题解：
//找出俩个链表的公共节点 public ListNode getIntersectionNode(ListNode headA, ListNode headB){ //先求俩个链表的长度 int lenA = 0; int lenB = 0; ListNode pl = headA; ListNode ps = headB; while(pl != null){ lenA++; pl = pl.next; } while(ps != null){ lenB++; ps = ps.next; } pl = headA; ps = headB; int len = lenA - lenB; if(len < 0){ pl = headB; ps = headA; len = lenB - lenA; } //让长的链表先走len步 while(len != 0 ){ pl = pl.next; len--; } //再一起走，相遇的节点就是想要的答案 while(pl != ps){ pl = pl.next; ps = ps.next; } return pl; }
代码剖析：
- pl代表最长的链表，ps永远是短的链表。
第12题：
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
题解：
//判断链表是否有环 public boolean hasCycle(){ 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 boolean hasCycle(){ 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 false; } return true; }
代码剖析：
- 本题用到快慢指针和追及问题。
第13题：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
题解：
//链表若有环，返回入环的第一个节点，无则null public ListNode detectCycle() { 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; } slow = head; while(fast != slow){ fast = fast.next; slow = slow.next; } return fast; }
代码剖析：
- 如果起始点到入口距离为X，相遇点到入口距离为Y，环的长度为C，则 X=Y。
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
如果对您有帮助的话，
不要忘记点赞+关注哦，蟹蟹
