通過遞歸實(shí)現(xiàn)創(chuàng)建一個(gè)鏈表
Node節(jié)點(diǎn)的定義
public class Node {
private final int value;
private Node next ;
public Node(int value)
{
this.value = value;
next = null;
}
public int getValue() {
return value;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public static void printLinkedList(Node node)
{
while (node!=null)
{
System.out.print(node.getValue());
System.out.print(" ");
node = node.getNext();
}
System.out.println();
}
}
遞歸創(chuàng)建鏈表
public Node createLinkedList(List<Integer> data)
{
if (data.isEmpty())
{
return null;
}
Node firstNode = new Node(data.get(0));
firstNode.setNext(createLinkedList(data.subList(1,data.size())));
return firstNode;
}
給定value值刪除鏈表中出現(xiàn)的所有節(jié)點(diǎn)兴使，存在多個(gè)相同節(jié)點(diǎn)的情況。
注意點(diǎn)：
- 頭節(jié)點(diǎn)就出現(xiàn)匹配的數(shù)據(jù)照激，而且不止一個(gè)
- 刪除節(jié)點(diǎn)的思想：改變next的指向
- 找出共同處理的地方使用循環(huán)的思想解決
public Node deleteIfValue(Node head,int value){
//特殊情況发魄，頭節(jié)點(diǎn)存在匹配value的情況
while (head!=null&&head.getValue()==value)
{
head = head.getNext();
}
if (head==null)
{
return null;
}
//定義出一個(gè)指針
Node pre = head;
while (pre.getNext()!=null)
{
if (pre.getNext().getValue()==value)
{
pre.setNext(pre.getNext().getNext());
}else {
pre = pre.getNext();
}
}
return head;
}
利用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列的操作
棧的存儲(chǔ)特點(diǎn)是后進(jìn)先出，所以兩個(gè)棧一個(gè)作為壓棧使用俩垃，另一個(gè)作為彈出励幼，但是要注意的一點(diǎn)就是需要保證棧1的元素都完全倒入到棧2中。
兩個(gè)各司其職的棧
- 如果stackPush要往stackPop中壓入數(shù)據(jù)口柳，那么久必須把stackPush中的元素全部壓入苹粟。
- 如果stackPop中不為空，那么就不可以往stackPop壓入元素跃闹。
public class StackQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;
public StackQueue()
{
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
//隊(duì)列進(jìn)隊(duì)
public void add(Integer i)
{
stackPush.push(i);
}
//隊(duì)列的poll方法
public int poll()
{
if (stackPop.empty()&&stackPush.empty())
{
System.out.println("隊(duì)列為空嵌削。");
}
else if (stackPop.empty())
{
while (!stackPush.empty())
{
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
//隊(duì)列的peek方法
public int peek()
{
if (stackPop.empty()&&stackPush.empty())
{
System.out.println("隊(duì)列為空毛好。");
}else if (stackPop.empty())
{
while (!stackPush.empty())
{
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}
判斷一個(gè)鏈表是不是回文的結(jié)構(gòu)
題目：給定一個(gè)鏈表的頭結(jié)點(diǎn)head，請判斷該鏈表是不是回文的結(jié)構(gòu)苛秕？
解決思路：利用棧的存儲(chǔ)后進(jìn)先出的特點(diǎn)進(jìn)行回文的判定
//鏈表節(jié)點(diǎn)的定義
class LinkedNode
{
int value;
LinkedNode next = null;
LinkedNode(int value)
{
this.value = value;
}
}
public boolean isPalindrome(LinkedNode head)
{
if (head==null){
return false;
}
Stack<Integer> stack = new Stack<Integer>();
LinkedNode cur = head;
//將鏈表的數(shù)據(jù)壓入棧中
while (cur!=null)
{
stack.push(cur.value);
cur = cur.next;
}
//出棧進(jìn)行回文判斷
while (head!=null)
{
if (head.value!=stack.pop())
{
return false;
}
head = head.next;
}
return true;
}
刪除一個(gè)鏈表中重復(fù)出現(xiàn)的節(jié)點(diǎn)
題目： 給定一個(gè)無序單鏈表的頭節(jié)點(diǎn)head肌访，刪除其中值重復(fù)出現(xiàn)的節(jié)點(diǎn)。
例如：1->2->3->3->4->4->2->1->1->null艇劫，刪除值重復(fù)的節(jié)點(diǎn)之后為
1->2->3->4->2->1->null
解決思路：
- 生成一個(gè)哈希表吼驶，因?yàn)轭^節(jié)點(diǎn)是不用刪除的節(jié)點(diǎn)，所以首先將頭節(jié)點(diǎn)的值存放入哈希表
- 從頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始往后遍歷節(jié)點(diǎn)港准，假設(shè)當(dāng)前遍歷到cur節(jié)點(diǎn)旨剥，先檢查cur的值是否在哈希表中，如果在浅缸，則說明cur節(jié)點(diǎn)的值是之前出現(xiàn)過的轨帜，就將cur節(jié)點(diǎn)刪除，刪除的方式是將最近一個(gè)沒有被刪除的節(jié)點(diǎn)pre連接到cur的下一個(gè)節(jié)點(diǎn)衩椒，即pre.next = cur.next.如果不在蚌父，將cur節(jié)點(diǎn)的值加入哈希表，同時(shí)令pre=cur毛萌，即更新最近一個(gè)沒有被刪除的節(jié)點(diǎn)苟弛。
public void DeleteListNode(LinkedNode head)
{
//如果頭結(jié)點(diǎn)是空的話結(jié)束程序
if (head==null)
{
return ;
}
//初始化
LinkedNode pre = head;
LinkedNode cur = head.next;
HashSet<Integer> set = new HashSet<Integer>();
set.add(head.value);
while (cur!=null)
{
if (set.contains(cur.value))
{
pre.next = cur.next;
}
else
{
set.add(cur.value);
pre = cur;
}
cur = cur.next;
}
打印兩個(gè)有序鏈表的公共節(jié)點(diǎn)
題目：提供兩個(gè)有序鏈表的頭指針head1和head2，打印兩個(gè)鏈表的公共部分阁将。
public void print(LinkedNode head1,LinkedNode head2)
{
while (head1!=null&&head1!=null)
{
if (head1.value<head2.value)
{
head1=head1.next;
}else if (head1.value>head2.value)
{
head2=head2.next;
}else
{
System.out.println(head1.value);
head1 = head1.next;
head2 = head2.next;
}
}
}
反轉(zhuǎn)鏈表
題目：輸入一個(gè)鏈表膏秫，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素做盅。
解題思路：
- 當(dāng)前節(jié)點(diǎn)是head缤削，pre為當(dāng)前節(jié)點(diǎn)的前?節(jié)點(diǎn)，next為當(dāng)前節(jié)點(diǎn)的下?節(jié)點(diǎn)
- 需要pre和next的?目的是讓當(dāng)前節(jié)點(diǎn)從pre->head>next1->next2變成pre<-head next1->next2
- 先保存head.next的節(jié)點(diǎn)吹榴，然后將head.next=pre換成前一個(gè)節(jié)點(diǎn)的引用
- 然后pre = head,head = next亭敢，進(jìn)行節(jié)點(diǎn)的遍歷替換
- 如果head為null的時(shí)候，pre就為最后一個(gè)節(jié)點(diǎn)了了图筹，但是 鏈表已經(jīng)反轉(zhuǎn)完畢帅刀，pre就是反轉(zhuǎn)后鏈表的第一個(gè)節(jié)點(diǎn)
public LinkedNode reverse(LinkedNode head)
{
if (head==null)
{
return null;
}
//初始化前后指標(biāo)節(jié)點(diǎn)
LinkedNode pre = null;
LinkedNode next = null;
while (head!=null)
{
next = head.next;
head.next = pre;
//head--> null
pre = head;
head = next;
}
return pre;
}
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)远剩。
- 這道題的難點(diǎn)在于不不知道k結(jié)點(diǎn)的位置扣溺。
- 我們可以使?用兩個(gè)指針，第一個(gè)指針先跑k-1 ,然后兩個(gè)指針再一起跑
- 等到第一個(gè)指針到終點(diǎn)時(shí)瓜晤，第二個(gè)指針距終點(diǎn)也就是倒數(shù)第k個(gè)結(jié)點(diǎn)
定義兩個(gè)指針娇妓，我們都知道倒數(shù)第k個(gè)距離最后一個(gè)的距離是k-1，所以可以先移動(dòng)一個(gè)指針走k步后活鹰，然后兩個(gè)指針同時(shí)移動(dòng)哈恰，那么在快的指針到達(dá)結(jié)尾時(shí)，慢的指針到達(dá)的位置正好是倒數(shù)第k個(gè)志群。
public LinkedNode FindKthNode(LinkedNode head,int k)
{
//定義兩個(gè)指針
LinkedNode point1 = head;
LinkedNode point2 = head;
int a = k;//記錄k值的變化
int count = 0;//記錄節(jié)點(diǎn)的數(shù)目
while (point1!=null)
{
point1 = point1.next;
count++;
if (k<1) //說明此事point1已經(jīng)到正向k的位置
{
point2 = point2.next; //指針2開始
}
k--; //point1每次走一次都要減去1
}
if (count<a)
//如果節(jié)點(diǎn)個(gè)數(shù)?小于所求的倒數(shù)第k個(gè)節(jié)點(diǎn)着绷，則返回null
{
return null;
}
return point2;
}
附加
二分查找
注意點(diǎn)：
- mid的計(jì)算方式采用a+(b-a)/2
- 理由是：當(dāng)a和b的值過大的情況會(huì)出現(xiàn)溢出的情況，所以這里采用改進(jìn)
public static int binSearch(int[] arr,int k){
int low = 0;
int high = arr.length;
//注意high的取值是arr.length或arr.length-1,對(duì)于循環(huán)體的處理不同
while (high>low)
{
int mid = low+(high-low)/2; //(low+high)/2 當(dāng)兩個(gè)數(shù)很大的情況可能出現(xiàn)溢出
if (arr[mid]>k) // [low,mid)
{
high = mid;
}else if (arr[mid]<k)
{
low = mid+1;
}else
return mid;
}
return -1;
}
樹的定義
package com.joyo.code;
public class TreeNode {
private final char value;
private TreeNode left;
private TreeNode right;
public TreeNode(char value) {
this.value = value;
this.left = null;
this.right = null;
}
public char getValue() {
return value;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
}
創(chuàng)建樹
二叉樹
public TreeNode treeCreator()
{
TreeNode root = new TreeNode('A');
root.setLeft(new TreeNode('B'));
root.getLeft().setLeft(new TreeNode('D'));
root.getLeft().setRight(new TreeNode('E'));
root.getLeft().getRight().setLeft(new TreeNode('G'));
root.setRight(new TreeNode('C'));
root.getRight().setRight(new TreeNode('F'));
return root;
}
樹的遍歷（前序锌云、中序荠医、后序）
主要還是通過遞歸的思想來進(jìn)行遍歷，前中后就是調(diào)整語句的執(zhí)行順序
前序
//前序遍歷
public static void preOrder(TreeNode root){
if (root==null)
{
return;
}
System.out.print(root.getValue());
preOrder(root.getLeft());
preOrder(root.getRight());
}
中序
//中序遍歷
public void inOrder(TreeNode root){
if (root==null)
{
return;
}
inOrder(root.getLeft());
System.out.print(root.getValue());
inOrder(root.getRight());
}
后序
//后續(xù)遍歷
public void postOrder(TreeNode root){
if (root==null)
{
return;
}
postOrder(root.getLeft());
postOrder(root.getRight());
System.out.print(root.getValue());
}
輸出結(jié)果：
前序：ABDEGCF
中序：DBGEACF
后序：DGEBFCA
根據(jù)前序中序輸出后序
注意點(diǎn)：
- 縮小范圍桑涎，尋找遞歸的執(zhí)行區(qū)域
-
前序和中序可以確認(rèn)樹的結(jié)構(gòu)彬向，但是前序和后序無法唯一性確定好二叉樹的結(jié)構(gòu)
遞歸縮小求解范圍
public String postPrint(String pre,String in){
if (pre.isEmpty()){
return "";
}
char rootNode = pre.charAt(0);
int indexNode = in.indexOf(rootNode);
return postPrint(pre.substring(1,indexNode+1),in.substring(0,indexNode))+
postPrint(pre.substring(indexNode+1),in.substring(indexNode+1))+
rootNode;
}
