单链表的基本操作

ゝ一世哀愁。 2023-06-24 06:26 13阅读 0赞

##### 一、向链表中插入数据 #####

1.  首先先创建一个节点，判断头节点是否为空，如果为空的话就将将新节点付给头节点，如果不为空的话遍历找出尾节点，将新节点赋给为节点的后继节点。

public class Node {
        
    	Node next = null;
    	int data;
    	public Node(int data) {
        
    		this.data = data;
    	}
    
    }
    **************************************
    //插入
    	public void add(int dex) {
        
    		//创建节点
    		Node newNode = new Node(dex);
    		//判断头节点是否为空，为空的话将新节点赋值给头节点
    		if(head == null) {
        
    			head = newNode;
    			return;
    		}
    		//遍历找出尾节点，将新节点赋给为尾节点的后继节点
    		Node tmp = head;
    		while(tmp.next != null) {
        
    			tmp = tmp.next;
    		}
    		tmp.next = newNode;
    		
    	}
    *************************************
    public static void main(String[] arge) {
        
    		//创建一个单链表
    		MyLinkedList ml = new MyLinkedList();
    		ml.add(1);
    		ml.add(3);
    		ml.add(2);
    		ml.add(4);
    		ml.add(3);
    		System.out.println("添加数据后的链表：");
    		ml.printList();
    }

1.  运行截图：  
    ![在这里插入图片描述][20191221104908112.png]

##### 二、删除链表中的第index个节点 #####

1.  流程如下  
    （1）首先判断需要删除的节点的位置是否合理，不合理直接的返回false。  
    （2）判断需要删除的节点是否为为头节点，如果是头节点的话，将头节点的后继节点直接付给它本身，返回true.  
    （3）不是头节点的话，定义一个当前节点和当前节点内的下一个节点，判断是否为第二个节点，是的话直接将下一个节点的后继节点赋给当前节点的下一个节点，返回true。  
    （4）如果不是第二个节点的话，将下一个节点赋给当前节点，将下一个节点的后继节点赋给它本身，然后变量自增
2.  代码如下：

//删除
    	public Boolean delect(int index) {
        
    		
    		//判断需要删除节点的下标是否不合理
    		if(index<0||index>length()) {
        
    			return false;
    		}
    		
    		//删除第一个节点
    		if(index ==1) {
        
    			head = head.next;
    			return true;
    		}
    		
    		int i=1;
    		//定义当前节点
    		Node preNode = head;
    		//当前节点的下一个节点
    		Node curNode = preNode.next;
    		while(curNode != null) {
        
    			//将下一个节点的后继节点赋值给当前节点的下一个节点
    			preNode.next = curNode.next;
    		}
    		//将下一个节点赋值给当前节点
    		preNode = curNode;
    		//将当前节点的下一个节点的后继节点赋值给它本身
    		curNode = curNode.next;
    		i++;
    		return true;
    	}
    	******************************************************
    	System.out.println("删除节点前：");
    		ml.printList();
    		ml.delect(3);
    		System.out.println("删除节点后：");
    		ml.printList();

1.  运行截图：  
    ![在这里插入图片描述][20191221114155128.png]

##### 三、删除重复的节点 #####

1.  基本步骤：两次遍历循环，外层循环遍历的节点与内层循环遍历的节点对比，如果遇到相同的节点，就删除。
2.  代码如下：

//删除重复的元素
    	public void deleteDuplecate(Node head) {
        
    		Node p = head;
    		while(p != null) {
        
    			Node q = p;
    			while(q.next != null ) {
        
    				if(p.data ==q.next.data) {
        
    					q.next = q.next.next;
    				}else {
        
    					q = q.next;
    				}
    				
    			}
    			p = p.next;
    			
    		}
    		
    	}

1.  运行截图：  
    ![在这里插入图片描述][20191221115125470.png]

##### 四、返回链表的长度 #####

1.  代码如下：

//节点长度
    	public int length() {
        
    		int length = 0;
    		Node tmp = head;
    		while(tmp != null) {
        
    			tmp = tmp.next;
    			length++;
    		}
    		return length;
    	}

1.  运行截图：  
    ![在这里插入图片描述][20191222120823950.png]

##### 五、对链表进行排序 #####

1.  基本原理：该排序方法采用了冒泡排序的方法，外层循环遍历当前节点，内层循环遍历下一个节点，如果前一个节点的值大于后一个，则调换位置，最后返回头节点。
2.  代码如下：

//对链表进行排序
    	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;
    	}

3 .运行截图：  
![在这里插入图片描述][20191222121648181.png]

##### 六、如何找出链表中的倒数第k个元素 #####

1.  基本原理：设置两个指针，让其中一个指针比另外一个先移**k-1**步，然后两个指针系统是先前移动，循环到先行的指针为空的时候，林外一个指针所指的位置就是单数第k个位置。
2.  代码如下：

//找出单链表中倒数第k个元素
    	public Node findElem(int k) {
        
    		
    		if(k<1)
    			return null;
    		Node p1 = head;
    		Node p2 = head;
    		//循环让p1先走k-1步
    		for(int i=0;i<k-1&&p1 != null;i++) {
        
    			p1 = p1.next;
    		}
    		if(p1 ==null) {
        
    			System.err.println("k不合法");
    			return null;
    		}
    		//同时移动
    		while(p1.next != null) {
        
    			p1 = p1.next;
    			p2 = p2.next;
    		}
    		
    		return p2;
    	}

1.  运行截图：  
    ![在这里插入图片描述][20191222122524333.png]

##### 七、从头到尾输出单链表 #####

1.  基本原理：要实现反过来输出链表，每访问到一个节点，先递归输出它后面的节点，在输出节点本身。
2.  代码如下：

//从尾到头输出单链表
    	public void printListReversely(Node head) {
        
    		//先递归输出最后一个节点，再一次输出前面的节点
    		if(head != null) {
        
    			printListReversely(head.next);
    			System.out.println(head.data);
    		}
    	}

1.  运行截图：  
    ![在这里插入图片描述][2019122212343353.png]

##### 八、寻找单链表的中间节点 #####

1.  基本原理：用两个指针从头到尾遍历，快指针一次走两步，慢指针一次走一步，快指针到达尾部时慢指针到达中间位置（如果链表长度为奇数时，慢指针指向的就是中间节点。如果链表长度为偶数时，慢指针指向的节点和下一个节点都是中间节点）
2.  代码如下：

//寻找但单链表的中间节点
    	public Node SearchMid() {
        
    		//快指针
    		Node p = this.head;
    		//慢指针
    		Node q = this.head;
    		
    		while(p != null && p.next != null && p.next.next != null) {
        
    			//p走两步
    			p = p.next.next;
    			//q走一步
    			q = q.next;
    		}
    		return q;
    	}

1.  运行截图：  
    ![在这里插入图片描述][20191222124303814.png]

##### 九、判断一个链表是否有环 #####

1.  基本原理：两个指针都指向头节点，快指针一次走两步，慢指针一次走一步，每次移动相互比较，相等时证明该链表是带环的，否则反之。
2.  代码如下：

//检测一个链表是否有环
    	public boolean IsLoop(Node head) {
        
    		//快指针
    		Node fast = head;
    		//慢指针
    		Node slow = head;
    		
    		//判断快指针为空，返回false，链表无环
    		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);
    	}

1.  运行截图：  
    ![在这里插入图片描述][2019122212513323.png]

##### 十、在不知道头节点的情况下删除指定节点 #####

1.  基本原理：先判断是否为尾节点，如果是尾节点则无法删除，如果不是尾节点，则通过交换这个节点与其后继节点的值，来删除节点。
2.  代码如下：

//在不知道头节点的情况下删除指定节点
    	public boolean deleteNode(Node n) {
        
    		//判断非空
    		if(n == null || n.next == null) {
        
    			return false;
    		}
    		//交换与其后继节点的值
    		int tmp = n.data;
    		n.data = n.next.data;
    		n.next.data = tmp;
    		
    		//将当前节点的下下个节点赋给当前节点内的下一个节点
    		n.next = n.next.next;
    		
    		return true;
    	}

1.  运行截图：  
    ![在这里插入图片描述][20191222130845720.png]

##### 十一、判断两个链表是否相交 #####

1.  基本原理：如果两个链表相交，那么他们一定有着相同的尾节点。分别遍历两个链表，记录他们的尾节点，如果尾几点相同，那么两个链表相交，否则不想相交。
2.  代码如下：

//判断连个链表是否相交
    	public boolean isIntersect(Node h1,Node h2) {
        
    		//判断非空
    		if(h1 == null || h2 == null) {
        
    			return false;
    		}
    		
    		//找到链表h1的最后一个节点
    		Node tail1 = h1;
    		while(tail1.next != null) {
        
    			tail1 = tail1.next;
    		}
    		
    		//找到链表h2的最后一个节点
    		Node tail2 = h2;
    		while(tail2.next != null) {
        
    			tail2 = tail2.next;
    		}
    		
    		return (tail1 == tail2);
    		
    	}

##### 十二、链表反转（重点） #####

1.  基本原理：  
    （1）首先需要定义三个节点，即反转之后的头节点，当前节点，当前节点的前一个节点。  
    （2）将当前节点的后继节点保存起来，判断是否为空，为空的话将当前节点赋给反转后的头节点。  
    （3）反之，将当前节点指向前一个节点，整体下移，将当前节点赋给前一个结点，将但当前节点内的后继节点赋给当前节点。  
    （4）最后将反转后的头节点赋给头节点。
2.  代码如下：

//链表反转
    	public void ReverseIteratively() {
        
    		//反转后的头节点
    		Node pReversedHead = head;
    		//当前节点
    		Node pNode = head;
    		//当前节点的前一个节点
    		Node pPrev = null;
    		
    		//遍历
    		while(pNode != null) {
        
    			//先将当前节点的后一个节点存起来
    			Node pNext = pNode.next;
    			//判断当前节点的下一个节点为空的话就将当前节点赋给反转后的头节点
    			if(pNext != null) {
        
    				pReversedHead = pNode;
    			}
    			//将当前节点指向前一个节点
    			pNode.next = pPrev;
    			//整体下移
    			//当前节点赋给前一个结点
    			pPrev = pNode;
    			//将一开始存的下一个节点赋给当前节点内
    			pNode = pNext;
    		}
    		this.head = pReversedHead;
    	}

1.  运行截图：  
    ![在这里插入图片描述][20191222133824606.png]

[20191221104908112.png]: https://img-blog.csdnimg.cn/20191221104908112.png
[20191221114155128.png]: https://img-blog.csdnimg.cn/20191221114155128.png
[20191221115125470.png]: https://img-blog.csdnimg.cn/20191221115125470.png
[20191222120823950.png]: https://img-blog.csdnimg.cn/20191222120823950.png
[20191222121648181.png]: https://img-blog.csdnimg.cn/20191222121648181.png
[20191222122524333.png]: https://img-blog.csdnimg.cn/20191222122524333.png
[2019122212343353.png]: https://img-blog.csdnimg.cn/2019122212343353.png
[20191222124303814.png]: https://img-blog.csdnimg.cn/20191222124303814.png
[2019122212513323.png]: https://img-blog.csdnimg.cn/2019122212513323.png
[20191222130845720.png]: https://img-blog.csdnimg.cn/20191222130845720.png
[20191222133824606.png]: https://img-blog.csdnimg.cn/20191222133824606.png