Java 单向列表取倒数第n到m个元素？

红太狼 2022-10-15 11:48 170阅读 0赞

# Java 单向链表取倒数第n到m个元素 #

public class Test1 { 
    
    	static class ListNode { 
    		int value;
    		ListNode next;
    
    		ListNode(int value) { 
    			this.value = value;
    		}
    
    		ListNode add(int value) { 
    			ListNode n = new ListNode(value);
    			this.next = n;
    			return n;
    		}
    	}
    
    	// 取倒数第n到m个元素
    	public static void nthToLast(ListNode node, int n, int m) { 
    		ListNode head = null;
    		// 采用头插法，使列表倒序（类似于入栈）
    		while (node != null) { 
    			if (head == null) { 
    				head = node;
    				node = node.next;
    				head.next = null; // 倒叙最后一个节点没有next
    				continue;
    			}
    			ListNode temp = head; // 倒叙列表头临时存储
    			head = node; // 当前节点设置为头
    			node = node.next; // 循环遍历下一个节点
    			head.next = temp; // 设置头节点之后节点
    		}
    		System.out.println("倒序列表: " + p(head));
    		int count = 0;
    		ListNode nList = head;
    		StringBuffer sb = new StringBuffer();
    		while (nList != null) { 
    			count++;
    			if (count >= n && count <= m) { 
    				sb.append(nList.value).append(" -> ");
    			}
    			nList = nList.next;
    		}
    		System.out.println("倒数第" + n + "~" + m + "个元素：" + sb.toString());
    	}
    
    	// 打印列表
    	static String p(ListNode node) { 
    		StringBuffer sb = new StringBuffer();
    		while (node != null) { 
    			sb.append(node.value).append(" -> ");
    			node = node.next;
    		}
    		return sb.toString();
    	}
    
    	public static void main(String[] args) { 
    		ListNode listNode = new ListNode(1);
    		listNode.add(2).add(3).add(4).add(5).add(6);
    		System.out.println("原链表: " + p(listNode));
    		nthToLast(listNode, 1, 4);
    	}
    }
    
    
    原链表: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 
    倒序列表: 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 
    倒数第1~4个元素：6 -> 5 -> 4 -> 3 ->