链表 java实现
链表java实现：
因为面试/考试真的很喜欢考链表！！！
题目一：从尾到头打印链表
思路：利用stack【判断栈是否为空：!stack.isEmpty()】
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*/
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> stack=new Stack<>();
while(listNode!=null){
stack.push(listNode.val);
listNode=listNode.next;
}
ArrayList<Integer> list=new ArrayList<>();
while(!stack.isEmpty()){
list.add(stack.pop());
}
return list;
}
}
题目二：链表中倒数第k个结点
题目描述：输入一个链表，输出该链表中倒数第k个结点。
解法一：两次遍历，第一次统计链表中节点个数，第二次找到倒数的第k个节点
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null){
return head;
}
ListNode node=head;
int count=0;
while(node!=null){//统计链表长度
count++;
node=node.next;
}
if(count<k){
return null;
}
for(int i=0;i<count-k;i++){
head=head.next;
}
return head;
}
}
解法二：
只需一次遍历。两个链表指针，第一个先从链表头指针开始走k-1步，(注意判断链表长度是否达到了k，即node1.next!=null)；从第k步开始，第二个指针也从链表头指针开始，则当第一个达到结尾时（即while(node1.next!=null))，则第二个指针指向倒数第k个节点。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if(head==null||k==0){
return null;
}
ListNode node1=head;
ListNode node2=head;
for(int i=0;i<k-1;i++){
if(node1.next!=null){
node1=node1.next;
}
else{
return null;
}
}
while(node1.next!=null){
node1=node1.next;
node2=node2.next;
}
return node2;
}
}
相关题目：
求链表的中间节点？
若链表节点总数为奇数，则返回中间节点；偶数则返回中间2个任一个节点。可定义2个指针，同时从链表头结点出发，一个一次一步，一个一次两步，当快的到达末尾时，另一个在中间。
题目三：反转链表
题目描述：输入一个链表，反转链表后，输出新链表的表头。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head==null) return null;
ListNode pre=null;//存当前值,对于下一个来说就是前一个值，让它赋值给下一个head.next
ListNode next=null;//存下一个值
while(head!=null){
next=head.next;//next保存下一个指针
/*主要是让每次的head.next从指向下一位改为指向前一位pre,再让pre等于当前值，head等于next的值，
就可以从前往后使指针都指向它的前一位，从而实现反转链表*/
head.next=pre;
pre=head;
head=next;
}
return pre;//返回表头，即最后一次的当前值
}
}
题目四：合并两个排序的链表
题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路：递归，所以每次要判断如果list1 为空，返回list2；如果list2为空，返回list1；
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1==null){
return list2;
}else if(list2==null){
return list1;
}
ListNode pMergeHead = null;
if(list1.val<list2.val){
pMergeHead = list1;
pMergeHead.next = Merge(list1.next,list2);
}else{
pMergeHead = list2;
pMergeHead.next = Merge(list1,list2.next);
}
return pMergeHead;
}
}
题目五：两个链表的第一个公共节点
题目描述：输入两个链表，找出它们的第一个公共结点。
蛮力法：
时间复杂度：O(mn)
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null){
return null;
}
if(pHead2==null){
return null;
}
ListNode node=null;
while(pHead1!=null){
node=pHead2;
while(node!=null){
if(pHead1.val==node.val){
return pHead1;
}
node=node.next;
}
pHead1=pHead1.next;
}
return null;
}
}
辅助栈：
因为两个链表一定是从某个节点开始相同之后，都是重合的，呈Y型，所以只要从后往前找最后一个相同的节点即可。但链表都是从前往后的，所以需要两个辅助栈（栈后进先出）。
时间、空间复杂度：O(m+n)
第三种思路:(最好)
类似第二种，但不需要辅助栈。先遍历两个链表得到长度，比较。第二次遍历，在较长链表上先走若干步，再同时在两个链表上遍历，第一个相同节点就是公共节点。
时间空间：O(m+n)，但比第二张更提高了空间效率
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null){
return null;
}
if(pHead2==null){
return null;
}
ListNode node1=pHead1;
ListNode node2=pHead2;
int length1=0;
int length2=0;
//遍历两个链表得到其长度
while(node1!=null){
length1++;
node1=node1.next;
}
while(node2!=null){
length2++;
node2=node2.next;
}
//判断哪个链表较长，计算长的链表比短的链表多几个节点，使长链表先走若干步
int count=0;//计算多的节点
int minLength;//记录较短链表的长度
if(length1>length2){
count=length1-length2;
minLength=length2;
for(int i=0;i<count;i++){
pHead1=pHead1.next;
}
}else{
count=length2-length1;
minLength=length1;
for(int i=0;i<count;i++){
pHead2=pHead2.next;
}
}
//同时在两个链表上遍历，找出第一个相同的节点
for(int i=0;i<minLength;i++){
if(pHead1.val==pHead2.val){
return pHead1;
}
pHead1=pHead1.next;
pHead2=pHead2.next;
}
return null;
}
}
链表中环的节点：
题目描述：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
思路：
1、要先确定链表中是否有环。用两个指针，一个一次走一步p1，一个一次走两步 p2，如果走的快的追上了走的慢的，则有环。
2、得到环中节点数：p1走了x，p2走了2x，环的节点数n，则2x=x+n，所以n=x，p1实际走了一个环的长度
3、找到环的入口。p2指向头，p1不变，当p1==p2,则p1指向入口
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead==null||pHead.next==null){
return null;
}
ListNode p1=pHead;
ListNode p2=pHead;
while(p1!=null&&p2!=null){
p1=p1.next;
p2=p2.next.next;
if(p1==p2){
p2=pHead;
while(p1!=p2){
p1=p1.next;
p2=p2.next;
}
if(p1==p2){
return p1;
}
}
}
return null;
}
}
题目：删除链表中重复的节点
题目描述：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
思路：
1、需要两个指针，一个指向前一个节点preNode，另一个指向当前节点node，如果遇到相等的节点，node向后移动，preNode不动，存下node.val方便后面的比较，直到遇到node和node.next不相等，preNode就可以指向node.next
2、注意：链表开头可能就开始有重复的节点，所以默认preNode=null，在后面的给preNode赋值的时候，若preNode为null，那就把pHead设置为node.next
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode deleteDuplication(ListNode pHead)
{
//pHead存删后的节点
if(pHead==null){
return null;
}
ListNode preNode=null;//指向前一个节点
ListNode node=pHead;//当前节点
while(node!=null){
//值相等，则node向后移动，preNode不动，便于与后的值比较，直到遇到node和node.next.val不等的，preNode指向node.next
if(node.next!=null&&node.val==node.next.val){
int value=node.val;
//往后找，看是否还一样
while(node.next!=null&&node.next.val==value){
node=node.next;
}
if(preNode==null){//第一个就是重复的
pHead=node.next;
}else{//找到不相等的，preNode指向node.next
preNode.next=node.next;
}
}else{//没有重复的数，则preNode指向当前的值
preNode=node;
}
node=node.next;
}
return pHead;
}
}
链表总结：
链表通常要判断是否为空：
if(head==null) return head;
遍历链表： 链表一旦遍历则指针往下跳了，所以最好先赋值到另一个链表
while（head!=null){
head=head.next;
}
链表赋值：
已知ListNode head;
创建新链表 ListNode node=head;
