通过递归实现创建一个链表
Node节点的定义
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();
}
}
递归创建链表
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值删除链表中出现的所有节点，存在多个相同节点的情况。
注意点：
- 头节点就出现匹配的数据，而且不止一个
- 删除节点的思想：改变next的指向
- 找出共同处理的地方使用循环的思想解决
public Node deleteIfValue(Node head,int value){
//特殊情况，头节点存在匹配value的情况
while (head!=null&&head.getValue()==value)
{
head = head.getNext();
}
if (head==null)
{
return null;
}
//定义出一个指针
Node pre = head;
while (pre.getNext()!=null)
{
if (pre.getNext().getValue()==value)
{
pre.setNext(pre.getNext().getNext());
}else {
pre = pre.getNext();
}
}
return head;
}
利用两个栈实现一个队列的操作
栈的存储特点是后进先出，所以两个栈一个作为压栈使用，另一个作为弹出，但是要注意的一点就是需要保证栈1的元素都完全倒入到栈2中。
两个各司其职的栈
- 如果stackPush要往stackPop中压入数据，那么久必须把stackPush中的元素全部压入。
- 如果stackPop中不为空，那么就不可以往stackPop压入元素。
public class StackQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;
public StackQueue()
{
stackPush = new Stack<Integer>();
stackPop = new Stack<Integer>();
}
//队列进队
public void add(Integer i)
{
stackPush.push(i);
}
//队列的poll方法
public int poll()
{
if (stackPop.empty()&&stackPush.empty())
{
System.out.println("队列为空。");
}
else if (stackPop.empty())
{
while (!stackPush.empty())
{
stackPop.push(stackPush.pop());
}
}
return stackPop.pop();
}
//队列的peek方法
public int peek()
{
if (stackPop.empty()&&stackPush.empty())
{
System.out.println("队列为空。");
}else if (stackPop.empty())
{
while (!stackPush.empty())
{
stackPop.push(stackPush.pop());
}
}
return stackPop.peek();
}
}
判断一个链表是不是回文的结构
题目：给定一个链表的头结点head，请判断该链表是不是回文的结构？
解决思路：利用栈的存储后进先出的特点进行回文的判定
//链表节点的定义
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;
//将链表的数据压入栈中
while (cur!=null)
{
stack.push(cur.value);
cur = cur.next;
}
//出栈进行回文判断
while (head!=null)
{
if (head.value!=stack.pop())
{
return false;
}
head = head.next;
}
return true;
}
删除一个链表中重复出现的节点
题目： 给定一个无序单链表的头节点head，删除其中值重复出现的节点。
例如：1->2->3->3->4->4->2->1->1->null，删除值重复的节点之后为
1->2->3->4->2->1->null
解决思路：
- 生成一个哈希表，因为头节点是不用删除的节点，所以首先将头节点的值存放入哈希表
- 从头节点的下一个节点开始往后遍历节点，假设当前遍历到cur节点，先检查cur的值是否在哈希表中，如果在，则说明cur节点的值是之前出现过的，就将cur节点删除，删除的方式是将最近一个没有被删除的节点pre连接到cur的下一个节点，即pre.next = cur.next.如果不在，将cur节点的值加入哈希表，同时令pre=cur，即更新最近一个没有被删除的节点。
public void DeleteListNode(LinkedNode head)
{
//如果头结点是空的话结束程序
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;
}
打印两个有序链表的公共节点
题目：提供两个有序链表的头指针head1和head2，打印两个链表的公共部分。
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;
}
}
}
反转链表
题目：输入一个链表，反转链表后，输出链表的所有元素。
解题思路：
- 当前节点是head，pre为当前节点的前⼀节点，next为当前节点的下⼀节点
- 需要pre和next的⽬目的是让当前节点从pre->head>next1->next2变成pre<-head next1->next2
- 先保存head.next的节点，然后将head.next=pre换成前一个节点的引用
- 然后pre = head,head = next，进行节点的遍历替换
- 如果head为null的时候，pre就为最后一个节点了了，但是 链表已经反转完毕，pre就是反转后链表的第一个节点
public LinkedNode reverse(LinkedNode head)
{
if (head==null)
{
return null;
}
//初始化前后指标节点
LinkedNode pre = null;
LinkedNode next = null;
while (head!=null)
{
next = head.next;
head.next = pre;
//head--> null
pre = head;
head = next;
}
return pre;
}
输入一个链表，输出该链表中倒数第k个结点。
- 这道题的难点在于不不知道k结点的位置。
- 我们可以使⽤用两个指针，第一个指针先跑k-1 ,然后两个指针再一起跑
- 等到第一个指针到终点时，第二个指针距终点也就是倒数第k个结点
定义两个指针，我们都知道倒数第k个距离最后一个的距离是k-1，所以可以先移动一个指针走k步后，然后两个指针同时移动，那么在快的指针到达结尾时，慢的指针到达的位置正好是倒数第k个。
public LinkedNode FindKthNode(LinkedNode head,int k)
{
//定义两个指针
LinkedNode point1 = head;
LinkedNode point2 = head;
int a = k;//记录k值的变化
int count = 0;//记录节点的数目
while (point1!=null)
{
point1 = point1.next;
count++;
if (k<1) //说明此事point1已经到正向k的位置
{
point2 = point2.next; //指针2开始
}
k--; //point1每次走一次都要减去1
}
if (count<a)
//如果节点个数⼩小于所求的倒数第k个节点，则返回null
{
return null;
}
return point2;
}
附加
二分查找
注意点：
- mid的计算方式采用a+(b-a)/2
- 理由是：当a和b的值过大的情况会出现溢出的情况，所以这里采用改进
public static int binSearch(int[] arr,int k){
int low = 0;
int high = arr.length;
//注意high的取值是arr.length或arr.length-1,对于循环体的处理不同
while (high>low)
{
int mid = low+(high-low)/2; //(low+high)/2 当两个数很大的情况可能出现溢出
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;
}
}
创建树
二叉树
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;
}
树的遍历（前序、中序、后序）
主要还是通过递归的思想来进行遍历，前中后就是调整语句的执行顺序
前序
//前序遍历
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());
}
后序
//后续遍历
public void postOrder(TreeNode root){
if (root==null)
{
return;
}
postOrder(root.getLeft());
postOrder(root.getRight());
System.out.print(root.getValue());
}
输出结果：
前序：ABDEGCF
中序：DBGEACF
后序：DGEBFCA
根据前序中序输出后序
注意点：
- 缩小范围，寻找递归的执行区域
-
前序和中序可以确认树的结构，但是前序和后序无法唯一性确定好二叉树的结构
递归缩小求解范围
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;
}
网友评论