单链表原地反序 Posted on 2017-01-20 | In technology | | Visitors | 「原地」指的是除给出类之外,不借助其他的辅助结构 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061/** 带头指针的单链表原地逆序(逆序函数为reverse)* Created by Willow on 1/5/17.*/public class List { Node head; public List(Node head) { this.head = head; } //节点 static class Node { int data; Node next; public Node() {} public Node(int data, Node next) { this.data = data; this.next = next; } } //逆序 public void reverse() { if (null == head || null == head.next || null == head.next.next) return; Node pre = null, cur = this.head.next, nex = cur.next; while (null != nex) { //1. 逆置当前节点指向 cur.next = pre; //2. 前置、当前、后置节点的三个指针向前移动 pre = cur; cur = nex; nex = nex.next; } cur.next = pre;//3. 逆置最后一个节点的指向 this.head.next = cur;//4. 头指针指向最后一个节点 } //遍历 public void traverse() { if (null == head.next) return; Node cur = head.next; while (null != cur) { System.out.println(cur.data); cur = cur.next; } System.out.println("traverse end \n"); } //测试入口 public static void main(String[] args) { Node n7 = new Node(7, null); Node n6 = new Node(6, n7); Node n5 = new Node(5, n6); Node n4 = new Node(4, n5); Node n3 = new Node(3, n4); Node n2 = new Node(2, n3); Node n1 = new Node(1, n2); Node head = new Node(0, n1); List list = new List(head); list.traverse(); list.reverse(); list.traverse(); }} (EOF) 杨威 发布日期 :2017-01-20 自由转载-非商用-非衍生-保持署名(知识共享3.0许可证)