常考链表操作

1. 链表反转

改变指针方向，将头结点改为尾节点。本次给出全部代码，后来只给部分代码

class Node{

	int value;

	Node next=null;

	public Node(int value){

		this.value=value;

	}

}

public class linkedlisttest {

	Node head=null;

	public Node getHead() {

		return head;

	}

	public void insert(int data){

		Node newNode=new Node(data);

		if(head==null){

			head=newNode;

			return;

		}

		Node tmp=head;

		while(tmp.next!=null){

			tmp=tmp.next;

		}

		tmp.next=newNode;

		

		

	}

	public void printList() {

		Node tmp = head;

		

		while (tmp != null) {

			System.out.print(tmp.value+" ");

			tmp = tmp.next;

 

		}

	}

	//链表反转

		public void reverseListNode(Node head) {

			Node pReverseHead=head;//设置反转后的头结点

			Node pNode=head;//当前节点

			Node pPrev=null;//前一个节点

			while(pNode!=null){

				/*

				 * 例如i,m,n

				    由于反转需要改变指针的指向，但是一旦改变了指针的指向就没有指针指向下一个数，所以需要在改变i到m的指针顺序时

				    ，提前将下一个数存起来。

				*/

				Node pNext=pNode.next;//存储下一个节点

				if(pNext==null)

					pReverseHead=pNode;//令当前节点为反转链表的头结点

				

				pNode.next=pPrev;//将当前节点的下一个节点设为前一个节点

				

				pPrev=pNode;//前一个节点为当前节点

				pNode=pNext;//当前节点向下走

			}

			this.head=pReverseHead;

		}

	public static void main(String[] args) {

		linkedlisttest l=new linkedlisttest();

		l.insert(1);

		l.insert(2);

		l.insert(3);

		l.printList();

		System.out.println("\n链表反转：");

		l.reverseListNode(l.getHead());

		l.printList();

		

	}

 

}

运行结果：

2 .链表从尾到头输出

直接递归，等到后来二叉树三种遍历也是这个思想

public void printListReversely(Node plistHead){

			if(plistHead!=null){

				printListReversely(plistHead.next);

				System.out.print(plistHead.value+" ");

				

			}

			

		}

主函数：

	public static void main(String[] args) {

		linkedlisttest l=new linkedlisttest();

		l.insert(1);

		l.insert(2);

		l.insert(3);

		l.printList();

		System.out.println("\n链表从尾到头输出：");

		l.printListReversely(l.getHead());

		

		

	}

输出结果：

3. 判断链表是否有环

定义两个指针，一个快指针，一个慢指针，两个指针同时移动，快指针每次移动两步，慢指针移动一步，每次都比较，直到快指针等于慢指针为止。（fast先到底部为null则为无环链表）

public boolean Isloop(Node head){

		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 (fast!=null&&fast.next!=null);

	}

4. 如何删除重复元素

对链表进行双重遍历

public void deleteDuplecate(Node head){
		Node p=head;
		while(p!=null){
			Node q=p;
			while(q.next!=null){
				if(p.value==q.next.value){
					q.next=q.next.next;
				}else
					q=q.next;
			}
			p=p.next;
		}
	}

运行结果：

9.4 如何找到倒数第k个元素

设置两个指针，一个正常从头到尾遍历，另一个先前移k-1步然后依次遍历，当这个快指针先到达尾部，则另一个指针的位置就是倒数第k个元素。

主函数：

输出结果：

9.5 判断两个链表是否相交

如果相交则有相同的尾节点

public boolean isIntersect(Node h1,Node h2){

		if(h1==null||h2==null){

			return false;

		}

		Node tail=h1;

		Node tail2=h2;

		while(tail.next!=null){

			tail=tail.next;

		}

		while(tail2.next!=null){

			tail2=tail2.next;

		}		

		return tail==tail2;	

	}

9.6 链表排序

public Node orderlist() {

		Node nextNode = null;

		int temp = 0;

		Node curNode = head;

		while (curNode.next != null) {

			nextNode = curNode.next;

			while (nextNode != null) {

				if (curNode.data > nextNode.data) {

					temp = curNode.data;

					curNode.data = nextNode.data;

					nextNode.data = temp;

				}

				nextNode = nextNode.next;

			}

			curNode = curNode.next;

		}

		return head;

	}