数据结构_单向链表

╰半夏微凉° 2023-07-10 11:21 27阅读 0赞

### 文章目录 ###

*  节点定义
 *  单向链表定义
 *   *  属性、构造器
     *  打印链表
     *  通过索引获取节点
     *  末尾添加
     *  指定索引添加
     *  有序添加
     *  指定索引删除
     *  指定内容删除
     *  修改
     *  查询
 *  应用
 *   *  打印单向链表
     *  查询节点个数
     *  查询倒数第k个节点
     *  反转
     *  有序合并

# 节点定义 #

public class ListNode {
        
    	int val;
    	ListNode next;
    
    	public ListNode() {
        
    	}
    
    	public ListNode(int val) {
        
    		super();
    		this.val = val;
    	}
    
    	@Override
    	public String toString() {
        
    		return "ListNode [val=" + val + "]";
    	}
    }

# 单向链表定义 #

## 属性、构造器 ##

public class SingLinkedList {
        
    
    	private ListNode head;
    	private int size;
    
    	public SingLinkedList() {
        
    
    	}
    
    	public ListNode getHead() {
        
    		return head;
    	}
    
    	public int getSize() {
        
    		return size;
    	}
    }

## 打印链表 ##

public void list() {
        
    	ListNode cur = head;
    	while (cur != null) {
        
    		System.out.println(cur);
    		cur = cur.next;
    	}
    }

## 通过索引获取节点 ##

public ListNode getNode(int index) {
        
    	if (index < 0 || index >= size) {
        
    		return null;
    	}
    	ListNode cur = head;
    	for (int i = 0; i < index; i++) {
        
    		cur = cur.next;
    	}
    	return cur;
    }

## 末尾添加 ##

public void add(int val) {
        
    	ListNode node = new ListNode(val);
    	if (head == null) {
        
    		head = node;
    	} else {
        
    		getNode(size - 1).next = node;
    	}
    	size++;
    }

## 指定索引添加 ##

public void add(int index, int val) {
        
    	if (index < 0 || index > size - 1) {
        
    		throw new IndexOutOfBoundsException();
    	}
    	ListNode node = new ListNode(val);
    	if (index == 0) {
        
    		node.next = head;
    		head = node;
    	} else {
        
    		node.next = getNode(index);
    		getNode(index - 1).next = node;
    	}
    	size++;
    }

## 有序添加 ##

public void addByOrder(int val) {
        
    	ListNode node = new ListNode(val);
    	if (head == null) {
        
    		head = node;
    	} else if (val < head.val) {
        
    		node.next = head;
    		head = node;
    	} else {
        
    		ListNode pre = new ListNode();
    		pre.next = head;
    		while (pre.next != null && val > pre.next.val) {
        
    			pre = pre.next;
    		}
    		node.next = pre.next;
    		pre.next = node;
    	}
    	size++;
    }

## 指定索引删除 ##

public void deleteByIndex(int index) {
        
    	if (index < 0 || index > size - 1) {
        
    		throw new IndexOutOfBoundsException();
    	}
    	if (index == 0) {
        
    		head = head.next;
    	} else {
        
    		getNode(index - 1).next = getNode(index + 1);
    	}
    	size--;
    }

## 指定内容删除 ##

public void delete(int val) {
        
    	if (head == null) {
        
    		return;
    	}
    	if (head.val == val) {
        
    		head = head.next;
    		size--;
    		return;
    	}
    	ListNode pre = new ListNode();
    	pre.next = head;
    	while (true) {
        
    		if (pre.next == null) {
        
    			return;
    		}
    		if (pre.next.val == val) {
        
    			pre.next = pre.next.next;
    			size--;
    			return;
    		}
    		pre = pre.next;
    	}
    }

## 修改 ##

public void update(int index, int val) {
        
    	if (index < 0 || index > size - 1) {
        
    		throw new IndexOutOfBoundsException();
    	}
    	getNode(index).val = val;
    }

## 查询 ##

public int get(int index) {
        
    	if (index < 0 || index > size - 1) {
        
    		throw new IndexOutOfBoundsException();
    	}
    	return getNode(index).val;
    }

# 应用 #

## 打印单向链表 ##

public static void list(ListNode head) {
        
    	ListNode cur = head;
    	while (cur != null) {
        
    		System.out.println(cur);
    		cur = cur.next;
    	}
    }

## 查询节点个数 ##

public static int length(ListNode head) {
        
    	int count = 0;
    	ListNode cur = head;
    	while (cur != null) {
        
    		count++;
    		cur = cur.next;
    	}
    	return count;
    }

## 查询倒数第k个节点 ##

public static ListNode lastIndexOf(ListNode head, int lastIndex) {
        
    	if (head == null) {
        
    		return null;
    	}
    	if (lastIndex < 0 || lastIndex > length(head) - 1) {
        
    		return null;
    	}
    	ListNode cur = head;
    	for (int i = 0; i < length(head) - lastIndex - 1; i++) {
        
    		cur = cur.next;
    	}
    	return cur;
    }

## 反转 ##

public static ListNode reverse(ListNode head) {
        
    		ListNode newHead = new ListNode();
    		ListNode cur = head;
    		ListNode tmp = null;
    		while (cur != null) {
        
    			tmp = cur.next;
    			cur.next = newHead.next;
    			newHead.next = cur;
    			cur = tmp;
    		}
    		return newHead.next;
    	}

## 有序合并 ##

public static ListNode merge(ListNode l1, ListNode l2) {
        
    	ListNode newHead = new ListNode();
    	ListNode cur0 = newHead;
    	while (l1 != null && l2 != null) {
        
    		if (l1.val < l2.val) {
        
    			cur0.next = l1;
    			l1 = l1.next;
    		} else {
        
    			cur0.next = l2;
    			l2 = l2.next;
    		}
    		cur0 = cur0.next;
    	}
    	cur0.next = l1 == null ? l2 : l1;
    	return newHead.next;
    }