数据结构（一）手写单向链表

迈不过友情╰ 2023-07-04 12:37 23阅读 0赞

**1. 前沿**  
数据结构在实际工作中应用较多，大多框架都有应用，现特手写java中比较深奥的数据结构，本文是单向链表手写，希望对童鞋们的面试工作有帮助，现直接上代码如下.  
**2. 代码**

/**
     * Class: 基础数据结构-单向链表
     *
     * @Author: wz
     * @Date: 2020-02-09 16:01
     */
    public class MyNodeList {
        
    
    	/**
    	 * 单向链表节点
    	 */
    	private static class Node {
        
    		private int value;
    		private Node next;
    
    		private Node(int value) {
        
    			this.value = value;
    		}
    	}
    
    	/**
    	 * 头节点插入
    	 */
    
    	public static void headInsert(Node head, Node newNode) {
        
    		if (head != null) {
        
    			newNode.next = head;
    		}
    	}
    
    	/**
    	 * 尾节点插入
    	 *
    	 * @param tail
    	 * @param tailNode
    	 */
    	public static void tailInsert(Node tail, Node tailNode) {
        
    
    		if (tail != null) {
        
    			tail.next = tailNode;
    		}
    	}
    
    	/**
    	 * 插入
    	 *
    	 * @param s
    	 * @param p
    	 */
    	public static void insert(Node s, Node p) {
        
    		Node next = s.next;
    		s.next = p;
    		p.next = next;
    	}
    
    	/**
    	 * 根据节点值查找位置
    	 *
    	 * @param head
    	 * @param value
    	 * @return
    	 */
    	public static int find(Node head, int value) {
        
    		int count = 0;
    		while (head != null) {
        
    			if (head.value == value) {
        
    				return count;
    			}
    			//移动到下一位
    			head = head.next;
    			//下标加1
    			count++;
    		}
    		return count;
    	}
    
    	/**
    	 * 删除某一节点s,思路:把s的后驱节点的值赋值给s,删除s的后驱节点
    	 *
    	 * @param head
    	 * @param s
    	 */
    	public static void delete(Node head, Node s) {
        
    		//s节点后驱节点
    		Node old = s.next;
    		//s节点后驱节点的后驱节点
    		Node oldNext = old.next;
    		//如果s不是尾节点
    		if (old != null) {
        
    			//把s的后驱节点(old)的值赋值给s
    			s.value = old.value;
    			//指针指向下一个节点
    			s.next = oldNext;
    			//删除后驱节点
    			old = null;
    		}
    		//删除尾节点
    		else {
        
    			while (head != null && head.next != null) {
        
    				if (head.next.next == null && head.next == s) {
        
    					head.next = null;
    					break;
    				}
    				head = head.next;
    			}
    		}
    
    	}
    
    	/**
    	 * 链表反转
    	 *
    	 * @param head
    	 * @return
    	 */
    	public static Node reverse(Node head) {
        
    		Node pre = null;
    		Node next = null;
    		while (head != null) {
        
    			next = head.next;
    			//反转
    			head.next = pre;
    			pre = head;
    			head = next;
    		}
    		return pre;
    	}
    
    	/**
    	 * 取中间节点(偶数时取中间第一个)，两个节点，一个节点走一步，另外一个节点走两步
    	 * @param head
    	 * @return
    	 */
    	public static Node getMid(Node head) {
        
    		Node slow = head;
    		Node fast = head;
    		while (fast.next != null && fast.next.next != null) {
        
    			slow = slow.next;
    			fast = fast.next.next;
    		}
    		return slow;
    	}
    
    	/**
    	 * 链表排序(归并)
    	 * 将待排序数组（链表）取中点并一分为二；
    	 * 递归地对左半部分进行归并排序；
    	 * 递归地对右半部分进行归并排序；
    	 * 将两个半部分进行合并（merge）,得到结果。
    	 */
    	public static Node sortList(Node head) {
        
    		//采用归并排序
    		if (head == null || head.next == null) {
        
    			return head;
    		}
    		Node mid = getMid(head);
    		Node right = mid.next;
    		mid.next = null;
    		return merge2(sortList(head), sortList(right));
    	}
    
    
    	/**
    	 * 合并两个有序链表
    	 */
    	private static Node merge2(Node head1, Node head2) {
        
    		if (head1 == null && head2 == null) {
        
    			return null;
    		}
    		if (head1 == null) {
        
    			return head2;
    		}
    		if (head2 == null) {
        
    			return head1;
    		}
    		//合并的头节点
    		Node head = null;
    		if (head1.value < head2.value) {
        
    			head = head1;
    			head.next = merge2(head1.next, head2);
    		} else {
        
    			head = head2;
    			head.next = merge2(head1, head2.next);
    		}
    		return head;
    	}
    
    	/**
    	 * 遍历节点
    	 *
    	 * @param head
    	 */
    	public static void traverse(Node head) {
        
    		while (head != null) {
        
    			System.out.print(head.value + " ");
    			head = head.next;
    		}
    		System.out.println();
    	}
    
    	public static void main(String[] args) {
        
    		Node node1 = new Node(7);
    		Node node2 = new Node(2);
    		Node node3 = new Node(5);
    		Node node4 = new Node(4);
    		Node node5 = new Node(8);
    		Node node6 = new Node(1);
    		node1.next = node2;
    		node2.next = node3;
    		node3.next = node4;
    		node4.next = node5;
    		node5.next = node6;
    		node6.next = null;
    		traverse(sortList(node1));
    		tailInsert(node1, node3);
    		tailInsert(node3, node4);
    		System.out.println(getMid(node2).value);
    		traverse(node2);
    		Node a = reverse(node2);
    		while (a != null) {
        
    			System.out.print(a.value + " ");
    			a = a.next;
    		}
    	}
    }