高频面试算法题——链表

一、双向链表

package com.jp.yuanfudao.prepare.mianshi.test0616;

import com.sun.xml.internal.ws.api.message.Header;
import jdk.internal.org.objectweb.asm.tree.analysis.Value;

import java.io.IOException;
import java.util.Scanner;

/**
 * @program: mianjing
 * @description: 双向链表
 * @author: CoderPengJiang
 * @create: 2020-06-16 11:42
 **/
public class DoubleLinkNode {
    public Node head=null;
    public int length = 0;
    public static void main(String []args) throws IOException {
        DoubleLinkNode doubleLinkNode=new DoubleLinkNode();
        Scanner sc = new Scanner(System.in);
        while (true) {
            int s = sc.nextInt();
            if(s == 0) {
                break;
            }else {
                doubleLinkNode.addHead(s);
            }
        }
        //输入样例
        //1
        //2
        //3
        //0 输入0结束
        doubleLinkNode.printList();
        doubleLinkNode.deleteHead();
        doubleLinkNode.printList();

        Scanner in = new Scanner(System.in);
        int index = sc.nextInt();
        int data = sc.nextInt();
        doubleLinkNode.insertList(data, index);
        doubleLinkNode.printList();
    }


    //在链表的头部添加节点
    public void addHead(int data){
        Node newHead = new Node(data);
        if (head == null) {
            head=newHead;//如果链表为空，增加新结点
        }else{
            newHead.next=head;
            head.pre=newHead;
            head=newHead;
        }
        length ++;
    }

    //在链表的头部删除节点
    public void deleteHead(){
        if (head==null){
            System.out.println("空表，删除的节点不存在");
        }else {
            Node curNode=head;
            head=curNode.next;
            head.pre=null;
        }
        length--;
    }

    //在链表的尾部添加节点
    public void addTail(int data){
        Node newNode=new Node(data);
        if(head == null){
            head=newNode;
        }else {
            Node curNode = head;
            int count=1;
            while (count<length){
                curNode = curNode.next;
                count++;
            }
            newNode.next=null;
            newNode.pre=curNode;
            curNode.next=newNode;
        }
        length--;
    }

    //反向遍历链表
    public void printReverseNode(){
        if (head == null){
            System.out.println("空表");
        }
        Node curNode=head;
        while (curNode.next!=null){
            curNode=curNode.next;
        }
        while (curNode!=null){
            System.out.print(curNode+" ");
            curNode=curNode.pre;
        }
        System.out.println();
    }
    //在指定位置插入结点
    public void insertList(int data,int index){
        Node newNode=new Node(data);
        if (head == null){
            head=newNode;
        }
        if (index>length+1||index < 1){
            System.out.println("结点插入的位置不存在，可插入的位置为1到"+(length+1));
        }
        if (index==1){
            newNode.next=head;
            head.pre=newNode;
            head=newNode; //在链表头插入
        }else {
            Node preNode=head;
            int count=1;
            while (count < index-1){
                preNode=preNode.next;
                count++;
            }
            Node curNode=preNode.next;
            newNode.next=curNode;
            newNode.pre=preNode;
            preNode.next=newNode;
            if (curNode != null) {
                curNode.pre=newNode;
            }
            length++;
        }

    }

    //在指定的位置删除节点
    public void deleteList(int index) {
        if(index<1||index>length){
            System.out.println("结点删除的位置不存在，可删除的位置为1到"+length);
        }
        if (index==1){
            Node curNode=head;
            head = curNode.next;
            head.pre=null;
            length--;
        }else {
            Node preNode=head;
            int count = 1;
            while(count<index-1){
                preNode=preNode.next;
                count++;
            }
            Node curNode=preNode.next;
            preNode.next=curNode.next;
            if (curNode.next!=null){
                curNode.next.pre=preNode;
            }
            length--;
        }
    }

    //查找数据是否存在,与单链表一样
    public boolean containData(int data){
        if (head==null){
            System.out.println("空表");
            return false;
        }
        Node curNode=head;
        while (curNode.value!=data){
            if (curNode.next==null){
                System.out.println("结点数据不存在");
                return false;
            }
            curNode=curNode.next;
        }
        System.out.println("结点数据存在");
        return true;
    }
    //获取指定位置的数据，与单链表一样
    public void getIndexData(int index){
        if (head==null){
            System.out.println("空表");
        }
        if (index <1||index >length){
            System.out.println("结点位置不存在，可获取的位置为1到"+length);
        }
        Node curNode=head;
        int count=1;
        while (count!=index){
            curNode=curNode.next;
            count++;
        }
        System.out.println(curNode);
    }
    //修改指定位置的结点数据，与单链表一样
    public void updataIndexData(int index,int data){
        if (head == null){
            System.out.println("空表");
        }
        if (index >length||index<1){
            System.out.println("结点删除的位置不存在，可删除的位置为1到"+length);
        }
        Node curNode=head;
        int count = 1;
        while (count !=index){
            curNode=curNode.next;
            count++;
        }
        curNode.value= data;
    }

    //打印链表
    public void printList() {
        Node temp=head;
        while (temp != null) {
            System.out.print(temp.value+" ");
            temp=temp.next;
        }
        System.out.println();
    }
}

class Node {
      int value;
      Node pre;
      Node next;

    public Node(int value) {
        this.value = value;
    }

    public Node(int value, Node pre, Node next) {
        this.value = value;
        this.pre = pre;
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

二、链表反转

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        //非递归
       //ListNode curNode=head;
       //ListNode preNode=null;
       //ListNode temp=null;
       //while(curNode!=null){
       //    temp=curNode.next;
       //    curNode.next=preNode;
       //    preNode=curNode;
       //    curNode=temp;
       //}
       //return preNode;

       //递归
       if(head==null||head.next==null){
           return head;
       }
       ListNode curNode=reverseList(head.next);
       head.next.next=head;
       head.next=null;
       return curNode;
    }
}

三、链表中倒数第k个结点

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {

    //方法一、先求链表的长度，再遍历第（length-k+1）个点即为所求的结点
      // if(k<0){
      //     return null;
      // }
      // if(head==null||head.next==null){
      //     return head;
      // }
      // ListNode curNode=head;
      // int length=1;
      // while(curNode.next!=null){
      //     curNode=curNode.next;
      //     length++;
      // }
      // curNode=head;
      // int count=1;
      // while(count!=(length-k+1)){
      //     curNode=curNode.next;
      //     count++;
      // }
      // return curNode;

      //方法二、双指针
      ListNode before=head,last=head;
      //
      for(int i=0;i<k;i++){
          before=before.next;
      }
      while(before!=null){
          before=before.next;
          last=last.next;
      }
      return last;
      
    }
}

四、奇偶链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        //算法：将奇数结点和偶数结点单独分开然后再合并
        ListNode odd=head,even=head.next,evenHead=even;
        while(even!=null&&even.next!=null){
            odd.next=even.next;
            odd=odd.next;
            even.next=odd.next;
            even=even.next;
        }
        odd.next=evenHead;
        return head;
    }
}

五、删除排序链表中的重复元素

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        head.next=deleteDuplicates(head.next);
        return head.val == head.next.val ? head.next:head;
    }
}