链表 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;

链表 java实现

推荐阅读更多精彩内容