package com.appdemo;
import android.util.Log;
import java.util.Stack;
public class Node {
int value;//节点内容
Node next;//下一个节点
public Node(int value) {
this.value = value;
}
打印链表
public void show() {//输出所有节点
Node currentNode = this;
while (true) {
Log.w("TAG", "---all---" + currentNode.value);
//取出下一个节点
currentNode = currentNode.next;
//如果是最后一个节点
if (currentNode == null) {
break;
}
}
}
判断链表是否有环形
首先创建两个指针1和2，同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针1每次向下移动一个节点，让指针2每次向下移动两个节点，然后比较两个指针指向的节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。
在一个环形跑道上，两个运动员在同一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为跑道是环形的。
private void loop() {
// 构造链表 1->2->3->4->5->6-4;
Node a = new Node(1);
Node b = new Node(2);
Node c = new Node(3);
Node d = new Node(4);
Node e = new Node(5);
Node f = new Node(6);
a.next = b; b.next = c; c.next = d;
d.next = e;
e.next = f;
//f.next = d;//构造环形 4 // a.show();//输出所有节点
Log.w("TAG", "----" + isLoop(a));
}
public static boolean isLoop(Node head){
Node slow = head.next;
Node fast = head.next.next;
// 链表为空或者只有一个节点
if(slow == null || fast == null){
return false;
}
while(slow.next != null){
// 只有 两个节点，当然是不存在循环的
if(fast.next == null){
return false;
}
// 如果slow的数据域和fast的数据域相同，则表示有环
if(slow.value == fast.value){
return true;
}
// slow指针走一步，fast走两步
slow = slow.next;
fast = fast.next.next;
//如果fast走到最后为空，表示没有环
if(fast == null){
return false;
}
}
return false;
}
反转链表 递归
public Node reverse(Node head) {
//如果链表为空或者链表中只有一个元素
if (head == null || head.next == null) {
return head;
}
Node temp = head.next;
////先反转后面的链表，走到链表的末端结点
Node newHead = reverse(head.next);
//再将当前节点设置为后面节点的后续节点
temp.next = head;
head.next = null;
return newHead;
}
/**
* 1->2->3->4 原始链表
* 1,从第二个数据开始，间第二个的指针指向第一个，比喻2->1
* 2,将现有的头部 1转换成尾部，尾部的next为null
* 3，将从第二个node开始，循环next指向前一个
* 4，一直有个指针指向还没有反转的链表的头部
* 需要左中右三个指针
*/
public static Node reverseList(Node node) {
Node pre = null;
Node next = null;
while (node != null) {
next = node.next; //第二个节点
node.next = pre;//2 null
pre = node;//baocun 1 jiedian
node = next;
pre.show();//输出所有节点
Log.w("TAG", "----------------");
}
return pre;
}
删除某一个节点
public void removeNode() {
//通过当前节点找到下下一个节点
Node newNext = next.next;
//再把下一个节点赋值给当前节点的下一个节点
this.next = newNext;
}
插入某个节点,作为当前节点的下一个节点
public void addNode(Node node) {
//取出下一个节点，作为下下个节点
Node nextNode = next;
//把新节点作为单点节点的下一个节点
this.next = node;
//把下下个节点作为设置新节点的下一个节点
node.next = nextNode;
}
合并两个有序链表
public Node Merge(Node list1, Node list2) {
if (list1 == null) {
return list2;
} else if (list2 == null) {
return list1;
}
Node pMergeHead = null;
if (list1.value < list2.value) {
pMergeHead = list1;
pMergeHead.next = Merge(list1.next, list2);
} else {
pMergeHead = list2;
pMergeHead.next = Merge(list1, list2.next);
}
return pMergeHead;
}
输入一个链表，输出该链表中倒数第k个结点。
public Node FindKthToTail(Node head, int k) {
Node pre = null, p = null;
//两个指针都指向头结点
p = head;
pre = head;
//记录k值
int a = k;
//记录节点的个数
int count = 0;
//p指针先跑，并且记录节点数，当p指针跑了k-1个节点后，pre指针开始跑，
//当p指针跑到最后时，pre所指指针就是倒数第k个节点
while (p != null) {
p = p.next;
count++;
if (k < 1) {
pre = pre.next;
}
k--;
}
//如果节点个数小于所求的倒数第k个节点，则返回空
if (count < a) return null;
return pre;
}
两个栈实现一个队列
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack1.empty() && stack2.empty()) {
throw new RuntimeException("Queue is empty!");
}
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
}
}
