首先定义自定义结点类,存储节点信息:
- public class Node {
- Node next = null;
- int data;
- public Node(int data) {
- this.data = data;
- }
- }
获取链表长度:
- private int length() {
- int length = 0;
- Node temp = head;
- while (temp != null) {
- length++;
- temp = temp.next;
- }
- return length;
- }
打印链表:
- public void printMyList() {
- Node temp = this.head;
- while (temp != null) {
- System.out.print(temp.data);
- temp = temp.next;
- if (temp != null) {
- System.out.print("-->");
- } else {
- System.out.println();
- }
- }
- }
向链表中插入数据:
- public void addNode(int d) {
- Node node = new Node(d);
- if (head == null) {
- head = node;
- return;
- }
- Node temp = head;
- while (temp.next != null) {
- temp = temp.next;
- }
- temp.next = node;
- }
向链表中插入结点:
- public void addNode(Node node) {
- if (head == null) {
- head = node;
- return;
- }
- Node temp = head;
- while (temp.next != null) {
- temp = temp.next;
- }
- temp.next = node;
- }
在链表尾部添加另一个链表:
- public static void addList(MyLinkedList list, MyLinkedList afterlist) {
- Node thishead = list.head;
- Node addhead = afterlist.head;
- if (thishead == null) {
- thishead = addhead;
- return;
- }
- Node temp = thishead;
- while (temp.next != null) {
- temp = temp.next;
- }
- temp.next = addhead;
- }
从链表中删除指定位置的数据:
- public boolean deleteNode(int index) { //index:删除的元素的位置
- if (index < 1 || index > length()) {
- return false;
- }
- if (index == 1) {
- head = head.next;
- return true;
- }
- int i = 2;
- Node preNode = head;
- Node curNode = preNode.next;
- while (curNode != null) {
- if (i == index) {
- preNode.next = curNode.next;
- return true;
- }
- preNode = curNode;
- curNode = curNode.next;
- i++;
- }
- return true;
- }
对链表进行排序,返回排序后的头结点:
- public Node orderList() {
- Node nextNode = null;
- int temp = 0;
- Node headNode = head;
- while (headNode.next != null) {
- nextNode = headNode.next;
- while (nextNode != null) {
- if (headNode.data > nextNode.data) {
- temp = nextNode.data;
- nextNode.data = headNode.data;
- headNode.data = temp;
- }
- nextNode = nextNode.next;
- }
- headNode = headNode.next;
- }
- return head;
- }
从链表中删除重复数据 第一种方法
- public void deleteRepetition1(){
- Hashtable<Integer, Integer>hashtable=new Hashtable<>();
- Node temp=this.head;
- Node pre=null;
- while(temp!=null){
- if(hashtable.containsKey(temp.data))
- {
- pre.next=temp.next;
- }
- else
- {
- hashtable.put(temp.data, 1);
- pre=temp;
- }
- temp=temp.next;
- }
- }
从链表中删除重复数据 第二种方法:
- public void deleteRepetition2(){
- Node temp=head;
- while(temp!=null){
- Node i=temp;
- while(i.next!=null){
- if(temp.data==i.next.data)
- {
- i.next=i.next.next;
- }
- else
- {
- i=i.next;
- }
- }
- temp=temp.next;
- }
- }
找出单链表中的倒数第k个元素:
- public Node findLastElem(int k) {
- if (k < 1) {
- System.out.println("k不合法");
- return null;
- }
- if (head == null) {
- System.out.println("链表不包含元素");
- return null;
- }
- Node p1 = head;
- Node p2 = head;
- for (int i = 0; i < k - 1; i++) {
- p2 = p2.next;
- }
- while (p2.next != null) {
- p1 = p1.next;
- p2 = p2.next;
- }
- return p1;
- }
链表反转:
- public void reversal() {
- Node pReversalHead = this.head;
- Node pNode = this.head;
- Node pPrev = null;
- while (pNode != null) {
- Node pNext = pNode.next;
- if (pNext == null) {
- pReversalHead = pNode;
- }
- pNode.next = pPrev;
- pPrev = pNode;
- pNode = pNext;
- }
- this.head = pReversalHead;
- }
不反转链表,倒序输出链表元素:
- public void printReversalList(Node pHead) {
- if (pHead.next == null) {
- System.out.print(pHead.data);
- }
- if (pHead.next != null) {
- printReversalList(pHead.next);
- System.out.print("-->" + pHead.data);
- }
- }
寻找单链表中间节点:
- public Node searchMidNode() {
- Node pNode = this.head;
- Node qNode = this.head;
- while (pNode != null && pNode.next != null && pNode.next.next != null) {
- pNode = pNode.next.next;
- qNode = qNode.next;
- }
- return qNode;
- }
判断一个链表是否有环:
- public boolean isHaveLoop() {
- Node fast = head;
- Node slow = head;
- if (fast == null) {
- return false;
- }
- while (fast != null && fast.next != null) {
- fast = fast.next.next;
- slow = slow.next;
- if (fast == slow) {
- return true;
- }
- }
- return false;
- }
寻找环入口:
- public Node getLoopStart(MyLinkedList list) {
- //在链表头和相遇点分别设置一个指针,每次各走一步,两个指针必定相遇,且第一个相遇点为环入口
- Node slow = list.head;
- Node fast = list.head;
- while (slow.next != null && fast.next != null) {
- slow = slow.next;
- fast = fast.next.next;
- if (slow == fast) {
- break;
- }
- }
- while (slow != fast) {
- slow = slow.next;
- fast = fast.next;
- }
- return slow;
- }
在不知道头指针的情况下删除指定节点:
- public boolean deleteNode(Node node) {
- //此方法不能删除链表最后一个节点,因为无法使其前驱结点的next指向null;
- if (node == null || node.next == null) {
- return false;
- }
- node.data = node.next.data;
- node.next = node.next.next;
- return true;
- }
判断两个链表是否相交:
- public static boolean isIntersect(MyLinkedList list, MyLinkedList list2) {
- Node head1 = list.head;
- Node head2 = list2.head;
- if (head1 == null || head2 == null) {
- return false;
- }
- while (head1.next != null) {
- head1 = head1.next;
- }
- while (head2.next != null) {
- head2 = head2.next;
- }
- return head1 == head2;
- }
寻找两个链表相交的第一个节点:
- public static Node getFirstMeetNode(MyLinkedList list, MyLinkedList list2) {
- Node head1 = list.head;
- Node head2 = list2.head;
- if (isIntersect(list, list2) == false) {
- return null;
- }
- Node t1 = head1;
- Node t2 = head2;
- if (list.length() > list2.length()) {
- int d = list.length() - list2.length();
- while (d != 0) {
- t1 = t1.next;
- d--;
- }
- } else {
- int d = list2.length() - list.length();
- while (d != 0) {
- t2 = t2.next;
- d--;
- }
- }
- while (t1 != t2) {
- t1 = t1.next;
- t2 = t2.next;
- }
- return t1;
- }
来源: http://www.cnblogs.com/alternative/p/7783079.html