java链表排序和反转

﹏ヽ暗。殇╰゛Y 2024-04-17 05:21 90阅读 0赞

链表排序  
概念什么的都不说了。  
链表排序的原理：和普通的数据排序每什么不同，就是两个节点的数据比较一下大小，需要的话就把两个节点存储的数据对调一个，链表指针没有变，变了节点的数据。  
链表节点类：

public class ListNode{
    		int data;
    		ListNode next = null;
    		//构造函数
    		public ListNode(int val) {
    			this.data = val;
    		}
    	}

在这里插入代码片
    public ListNode bubbleSort(ListNode head) {
    		if(head == null || head.next == null) {
    			return head;
    		}
    		
    		ListNode cur = head;//当前节点设置为第一个节点
    		ListNode tail = null;//最后一个节点
    		
    		while(cur.next != tail) {
    			
    			while(cur.next != tail) {
    				if(cur.data > cur.next.data) {
    					int tmp = cur.data;
    					cur.data = cur.next.data;
    					cur.next.data = tmp;
    				}
    				cur = cur.next;
    			}
    			
    			tail = cur;//下一次遍历的尾结点是当前结点
    			cur = head;//遍历起始结点重置为头结点 
    		}
    		
    		return head;
    	}

输入的是链表头，输出的也是链表头，头没有变。  
排序方法为冒泡排序法。也可以用其它排序方法。

链表反转：方法不唯一。  
1.可以链表的数据都存储在一个数组中，再排序，重新组成链表。  
2.改变指针的指向。  
3.递归。  
第一种方法简单，但占用内存多，效率低。  
第二中方法最好。简单，容易理解。  
算法流程：  
准备3个节点变量，分别存储相邻的3个节点，没有第三个节点的话就是null.  
想象一些翻转后的链表是什么样子的，链表的相对位置都没有变，变的只有节点的指针指向。旧链表的头即新链表的尾，所有将链表头的指针指向null。然后将第二个节点的指向改为第一个节点。3个指针变量都下后移一位，再改变指针指向，直到第二个节点为空。新链表的头节点就是此时的第一个节点。

在这里插入代码片
    public ListNode reverseList(ListNode head) {
    		if(head == null || head.next == null) {//只有一个节点不需要反转
    			return head;
    		}
    		
    		ListNode cur = head;//当前节点
    		ListNode next = head.next;//下一个节点
    		ListNode nextnext = null;//下下个节点
    		
    		//反转后，原头节点变为新链表的尾节点，因此指针为空
    		head.next = null;
    		
    		while(next != null) {
    			nextnext = next.next;
    			
    			//新链表的下一个节点的指针不在指向下下个节点，而是指向它的前一个节点
    			next.next = cur;
    			
    			//移动指针位置，为下一次循环准备。当前cur节点为下一个节点，
    			//下一个节点为下下个节点，直到下下个节点为空.
    			cur = next;
    			next = nextnext;
    		}
    		head = cur;//新的头节点就是旧链表的尾节点，即下一个节点为空的节点。
    		return head;//头指针
    	}

链表遍历：

在这里插入代码片
    public void printList(ListNode head) {
    		ListNode curNode = head;//当前链表头节点
    		while(curNode != null) {
    			System.out.print(curNode.data + " ");
    			curNode = curNode.next;
    		}
    	}

创建链表：  
public ListNode insertNode(int data,ListNode head) \{  
ListNode node = new ListNode(data);//数据转化成节点

//链表头是否为空，为空，将此节点作为链表头
    	if(head == null) {
    		head = node;
    		return node;
    	}
    	
    	ListNode curNode = head;//当前链表节点
    	while(curNode.next != null) {//找到最后一个节点
    		curNode = curNode.next;
    	}
    	curNode.next = node;//将新建的节点添加到链表尾部
    	return head;//链表头不变
    }