Java 链表部分习题总结

• 一、链表的反转(Leedcode.206反转链表)
• 二、返回链表的中间节点(Leedcode.876 链表的中间节点)
• 三、返回链表倒数第K个节点
• 四、删除链表中所有给定值val的节点（Leetcode.203 移除链表元素）
• 五、删除链表重复节点
• 六、给定X的值分割链表
• 七、链表的回文结构
• 八、判断链表是否有环（Leedcode.141 环形链表）

一、链表的反转(Leedcode.206反转链表)

将一个链表进行反转，定义两个指针 一个代替头节点跑，另外一个指针是指向下一个节点。之后代替头节点的指针走向需要交换的节点进行类似头插法的操作，最终将链表反转。

class Solution {
    public ListNode reverseList(ListNode head) {
     if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode curNext = cur.next;
        head.next = null;
        cur = curNext;
        while (cur != null) {
            curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }
}

二、返回链表的中间节点(Leedcode.876 链表的中间节点)

如果链表是奇数个节点，返回中间节点
如果链表是偶数个节点，返回中间第二个节点
思路：定义快慢指针，快指针一次走两个节点，慢指针一次走一个节点，奇数节点fast.next等于null结束循环，偶数节点在fast等于null结束循环 之后慢指针就是想要的节点。

class Solution {
    public ListNode middleNode(ListNode head) {
         ListNode cur1=head;//慢指针
         ListNode cur2=head;//快指针
        while(cur2!=null&&cur2.next!=null){//奇数偶数节点都要判断
            cur1=cur1.next;
            cur2=cur2.next.next;
        }
  		return cur1;
    }
}

三、返回链表倒数第K个节点

题解：给定一个K值，返回倒数第K个节点
1.首先要判断k是否合法，要时间复杂度低的情况下不能先遍历一边链表求链表长度和K比较，用巧办法判断快指针是否等于null来降低时间复杂度。

public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
         if(k<=0||head==null){
            return null;
        }
        ListNode fast=head;//定义快指针
        ListNode slow=head;//定义慢指针
      while(k-1!=0){
          if(fast.next!=null){
              fast=fast.next;
              k--;
          }else {//一边遍历就能判断K值合法性
              System.out.println("你给的K值太大了");
              return null;
          }
      }
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        System.out.println(slow.val);
        return slow;
    }
}

四、删除链表中所有给定值val的节点（Leetcode.203 移除链表元素）

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
题解：定义一个前驱节点

public ListNode removeElements(ListNode head, int val) {
        if(head==null)return null;
    ListNode cur=head.next;
    ListNode prev=head;
    //遍历单链表的每一个节点
    while (cur!=null){
        if(cur.val==val){//这是你要删除的节点
            prev.next=cur.next;//将下一个地址值赋给prev
            cur=cur.next;
        }else{//不是删除的节点
            prev=prev.next;
            cur=cur.next;
        }
    }if(head.val==val){//如果头节点也是要删除的节点
        head=head.next;
    }
    return head;
    }

五、删除链表重复节点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

public class Solution {
    public ListNode deleteDuplication(ListNode pHead){
    ListNode tmpHead=new ListNode(-1);//定义傀儡节点 
        ListNode cur=pHead;
        ListNode newHead=tmpHead;//防止头节点也是被删除的节点
        while (cur!=null){
            if(cur.next!=null&&cur.val==cur.next.val){//值相同的情况
               while (cur.next!=null&&cur.val==cur.next.val){
                   cur=cur.next;
               }
                cur=cur.next;
            }else {//
                tmpHead.next=cur;
                tmpHead=tmpHead.next;
                cur=cur.next;
            }
        }
        tmpHead.next=null;//防止最后一个节点也是要删除的节点
        return newHead.next;
    }
}

六、给定X的值分割链表

给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
题解 定义小于x的头指针和尾指针 定义大于x的头指针和尾指针
之后考虑特殊情况 全部都是大于x的就返回as，还有最后一个节点不是大于x的，会放到小于x的里面，会导致ae.next!=null，需要将其置null;

public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode bs=null;//比x小的节点的头
        ListNode be=null;//比x小的节点的尾
        ListNode as=null;//比x大的节点的头
        ListNode ae=null;//比x大的节点的尾
        ListNode cur=pHead;
        while(cur!=null){
            if(cur.val<x){//比x小的值  不能改变原来的顺序就用尾插法
                if(bs==null){//第一次插入
                bs=cur;
                be=cur;
                }else {//非第一次插入
                    be.next=cur;
                    be=be.next;
                }
            }
            else {//比x大的值
            if(as==null){//第一次插入
                as=cur;
                ae=cur;
            }else {//非第一次插入
                ae.next=cur;
                ae=ae.next;
                }
            }
            cur=cur.next;
        }
        if(bs==null){//第一个链表没有数据
            return as;
        }
        be.next=as;
            if(as!=null){//防止最后一个节点.next不是null
                ae.next=null;
}
        return bs;
    }
}

七、链表的回文结构

链表的回文结构 就是正反看都是一样的 例如1 2 3 2 1 .找到链表的中间位置 ，之后反转后半部分链表 比较 （分为奇偶节点比较）

public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
 if(head==null){return false;}
        if(head.next==null){return true;}

       ListNode fast=head;//定义快慢指针寻找中间节点
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;//找到中间节点 反转链表

        while(cur!=null){//反转链表
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            if(head.next==slow){
                return true;
            }
            head=head.next;
            slow=slow.next;
        }
return true;
    }
}

八、判断链表是否有环（Leedcode.141 环形链表）

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

public boolean hasCycle(Node head){//判断链表是否有环  最后一个节点的地址与前面节点的地址相同 快慢指针  相遇否 每次走两步就是最快能找到的 走3，4步慢 而且不一定能相遇与环的大小有关
    Node fast=this.head;
    Node slow=this.head;
    while(fast!=null&&fast.next!=null){//判断是否有环 之后跑
        fast=fast.next.next;
        slow=slow.next;
        if(slow==fast){
            return true;
        }
    }
    return false;
}