数据结构——链表

一链表的概念及结构链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。二、无头单向非循环链表实现public interface Ilist { //头插法 public void addFirst(int data); //尾插法 public void addLast(int data); //任意位置插入,第一个数据节点为0号下标 public void addIndex(int index,int data); //查找是否包含关键字key是否在单链表当中 public boolean contains(int key); //删除第一次出现关键字为key的节点 public void remove(int key); //删除所有值为key的节点 public void removeAllKey(int key); //得到单链表的长度 public int size(); public void clear(); public void display(); public void createList(); }public class MySingleList implements Ilist { static class ListNode { public int val; public ListNode next; public ListNode(int val) { this.val val; } } public ListNode head; Override public void addFirst(int data) { ListNode node new ListNode(data); node.next head; head node; } Override public void addLast(int data) { ListNode node new ListNode(data); if (head null) { head node; return; } ListNode cur head; while (cur.next ! null) { cur cur.next; } cur.next node; } Override //在中间为止插入元素 public void addIndex(int index, int data) { //先需要判断插入位置是否合法 int len size(); if (index 0 || index len) { System.out.println(插入位置不合法); } //头插 if (index 0) { addFirst(data); } //尾插 if (index len) { addLast(data); } //在中间位置插入 ListNode cur head; while (index - 1 ! 0) { cur cur.next; index--; } ListNode node new ListNode(data); node.next cur.next; cur.next node; } Override //查找元素是否存在 public boolean contains(int key) { ListNode cur head; while (cur ! null) { if (cur.val key) { return true; } cur cur.next; } return false; } Override public void remove(int key) { if (head null) { return; } if (head.val key) { head head.next; } ListNode cur findNodeOfKey(key); if (cur null) { return; } ListNode del cur.next; cur.next del.next; } public ListNode findNodeOfKey(int key) { ListNode cur head; while (cur.next ! null) { if (cur.next.val key) { return cur; } cur cur.next; } return null; } Override public void removeAllKey(int key) { if (head null) { return; } //判断头节点前的节点 ListNode prev head; ListNode cur head.next; while (cur ! null) { if (cur.val key) { //开始删除 prev.next cur.next; cur cur.next; } else { prev cur; cur cur.next; } } //判断头节点 if (head.val key) { head head.next; } } Override public int size() { int len 0; ListNode cur head; while (cur ! null) { len; cur cur.next; } return len; } Override public void clear() { ListNode cur head; while (cur ! null) { ListNode curN cur.next; cur.next null; cur curN; } //删除头节点 head null; } Override public void display() { ListNode cur head; while (cur ! null) { System.out.print(cur.val ); cur cur.next; } System.out.println(); } public void createList() { ListNode node1 new ListNode(12); ListNode node2 new ListNode(23); ListNode node3 new ListNode(34); ListNode node4 new ListNode(45); ListNode node5 new ListNode(56); node1.next node2; node2.next node3; node3.next node4; node4.next node5; this.head node1; } }三LinkedList的实现package test1; //模拟实现双向链表 public class MyLinkedList implements Ilist{ static class LinkNode{ public int val; public LinkNode prev; public LinkNode next; public LinkNode(int val) { this.val val; } } public LinkNode last; public LinkNode head; Override public void addFirst(int data) { LinkNode node new LinkNode(data); //空 if (head null){ head last node; }else { node.next head; head.prev node; head node; } } Override public void addLast(int data) { LinkNode node new LinkNode(data); //链表为空 if (head null){ head last node; }else { last.next node; node.prev last; last node; } } Override public void addIndex(int index, int data) { LinkNode node new LinkNode(data); //判断插入位置的合法性 if (index 0 || index size()){ System.out.println(插入位置不合法); } //头插 if(index 0){ addFirst(data); } //尾插 if (index size()){ addLast(data); } //中间位置插入 LinkNode cur head; while (index ! 0){ cur cur.next; index--; } node.next cur; node.prev cur.prev; cur.prev.next node; cur.prev node; } Override public boolean contains(int key) { if (head null){ return false; } LinkNode cur head; while (cur ! null){ if (cur.val key){ return true; } cur cur.next; } return false; } Override public void remove(int key) { LinkNode cur head; while (cur ! null) { if (cur.val key) { //开始删除 if (cur head) { head head.next; if (head ! null) { head.prev null; } } else { cur.prev.next cur.next; //最后一个节点 if (cur.next null) { last last.prev; } else { cur.next.prev cur.prev; } } return; } cur cur.next; } } Override public void removeAllKey(int key) { LinkNode cur head; while (cur ! null) { if (cur.val key) { //开始删除 if (cur head) { head head.next; if (head ! null) { head.prev null; } } else { cur.prev.next cur.next; //最后一个节点 if (cur.next null) { last last.prev; } else { cur.next.prev cur.prev; } } } cur cur.next; } } Override public int size() { LinkNode cur head; int count 0; while (cur !null ){ cur cur.next; count; } return count; } Override public void clear() { LinkNode cur head; while (cur !null){ LinkNode curN cur.next; cur.prev null; cur.next null; cur curN; } head null; last null; } Override public void display() { LinkNode cur head; while (cur ! null){ System.out.print(cur.val ); cur cur.next; } } Override public void createList() { } }四ArrayList和LinkedList的区别五相关面试题的题解1反转一个单链表public ListNode reverseList(ListNode head) { if (head null) { return head; } ListNode cur head.next; head.next null; while (cur ! null) { ListNode curN cur.next; cur.next head; head cur; cur curN; } return head; }2给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则返回第二个中间结点。public ListNode middleNode(ListNode head) { if (head null){ return head; } ListNode fast head; ListNode slow head; while (fast !null fast.next !null){ fast fast.next.next; slow slow.next; } return slow; }3输入一个链表输出该链表中倒数第k个结点。public ListNode FindKthToTail(ListNode head, int k) { if (head null) { return null; } ListNode fast head; ListNode slow head; int count 0; while (count ! k-1 ) { fast fast.next; if (fast null) { return null; } count; } while (fast.next ! null) { fast fast.next; slow slow.next; } return slow; }4将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。public ListNode mergeTwoLists(ListNode headA, ListNode headB) { ListNode newHead new ListNode(-1); ListNode tmp newHead; while (headA ! null headB !null){ if (headA.val headB.val){ tmp.next headA; headA headA.next; tmp tmp.next; }else { tmp.next headB; headB headB.next; tmp tmp.next; } } if (headA ! null){ tmp.next headA; } if (headB ! null){ tmp.next headB; } return newHead.next; }5编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结点之前public ListNode partition(ListNode head, int x) { // write code here ListNode bs null; ListNode be null; ListNode as null; ListNode ae null; ListNode cur head; while (cur ! null) { if (cur.val x) { //第一次插入 if (bs null) { bs be cur; } else { be.next cur; be be.next; } } else { if (as null) { as ae cur; } else { ae.next cur; ae ae.next; } } cur cur.next; } //如果都是大于x if (bs null) { return as; } be.next as; //不段第二个节点是否为空都手动置为空 if (as ! null) { ae.next null; } return bs; }6. 链表的回文结构。public boolean chkPalindrome(ListNode head) { 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 curN cur.next; cur.next slow; slow cur; cur curN; } while (head ! slow){ if (head.val ! slow.val){ return false; } if (head.next slow){ return true; } head head.next; slow slow.next; } return true; }7给定一个链表判断链表中是否有环。public boolean hasCycle(ListNode head) { ListNode fast head; ListNode slow head; while (fast !null fast.next!null){ fast fast.next.next; slow slow.next; if (fast slow){ return true; } } return false; }