集合总结之单链表反转

墨蓝 2022-12-22 08:42 108阅读 0赞

### 概念简述 ###

单链表是一种链式存取的[数据结构][Link 1]，用一组地址任意的[存储单元][Link 2]存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素([数据元素][Link 3]的映象) +[ 指针][Link 4](指示后继元素[存储][Link 5]位置)，元素就是存储数据的存储单元，指针就是连接每个结点的[地址][Link 6]数据。

### 结点数据结构 ###

┌───┬───┐

│data │next │

└───┴───┘

*  data域--存放结点值的数据域
 *  next域--存放结点的直接后继的地址（位置）的指针域（链域）

链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked List）。单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定，单链表可以用头指针的名字来命名。  
终端结点无后继，故终端结点的指针域为空，即NULL。

**存储方法**

链接方式存储的线性表简称为链表（Linked List），链表的具体存储表示为：

① 用一组任意的[存储单元][Link 7]来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）；

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）  
链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构；

### 单链表反转示例 ###

1.实体定义

/**
     * @author LGH
     * @date 2020/11/18 13:54
     */
    @Data
    @AllArgsConstructor
    @NoArgsConstructor
    public class TestNode {
    
        /**
         * 数据域
         */
        private Integer data;
        /**
         * 指针域
         */
        private TestNode next;
    
        public TestNode(Integer data) {
            this.data = data;
        }
    }

2.生成链表

/**
     * @author LGH
     * @date 2020/11/18 13:58
     */
    @Data
    public class BuildChain {
    
        private  TestNode head;
    
        public BuildChain(int size) {
            TestNode head = new TestNode(0);
            TestNode cur = head;
            for (int i = 1; i < size; i++) {
                TestNode tmp = new TestNode(i);
                cur.setNext(tmp);
                cur = tmp;
            }
            this.head = head;
        }
    
        public static void main(String[] args) {
            TestNode head = new BuildChain(10).getHead();
            StringBuilder sb = new StringBuilder();
            TestNode cur = head;
            sb.append(cur.getData());
            while (null != cur.getNext()) {
                sb.append(" -> ");
                sb.append(cur.getNext().getData());
                cur = cur.getNext();
            }
            System.out.println(sb.toString());
        }
    }

3.反转链表方式

/**
         * 方法1 递归实现 当栈深度大于12000 则会出现StakOverflowError
         * 
         * @param head
         * @return
         */
        public static TestNode reverse1(TestNode head) {
            if (null == head || null == head.getNext())
                return head;
            TestNode revHead = reverse1(head.getNext());
            head.getNext().setNext(head);
            head.setNext(null);
            return revHead;
        }
    	/**
    	 * 以上即是递归实现的源码，但是需要考虑的问题是递归都在java栈中进行，
         *需要考虑jdk支持的栈的深度。在jdk1.8.0_91版本中，
         *当上述链表长度大于12000则会出现StackOverFlowError错误。
         *说明对于该版本jdk栈的深度不能大于12000。
    	 *
    	 /
    
    
        /**
         * 方法2 遍历实现 通用实现方法最好的方法是采用遍历的方式进行反转
         * 
         * @param head
         * @return
         */
         public static TestNode converseChain(TestNode node){
            if (null == node){
                return null;
            }
    
            TestNode preNode = node;
            TestNode currentNode = node.getNext();
            while (null != currentNode.getNext()){
                TestNode tempNode = currentNode.getNext();
                currentNode.setNext(preNode);
                preNode = currentNode;
                currentNode = tempNode;
            }
            currentNode.setNext(preNode);
            node.setNext(null);
            return currentNode;
        }
    
    
    
        /**
         * 方法3 利用其他数据结构 stack 考虑到stack具有先进后出这一特性，因此可以借助于stack数据结构来实现单向链表的反转。
         * @param head
         * @return
         */
        public static TestNode reverse3(TestNode head) {
            Stack<TestNode> stack = new Stack<TestNode>();
            for (TestNode node = head; null != node; node = node.getNext()) {
                stack.add(node);
            }
            TestNode reHead = stack.pop();
            TestNode cur = reHead;
            while(!stack.isEmpty()){
                cur.setNext(stack.pop());
                cur = cur.getNext();
                cur.setNext(null);
            }
            return reHead;
        }

**如有披露或问题欢迎留言或者入群探讨**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDcwNzMz_size_16_color_FFFFFF_t_70][]

[Link 1]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450
[Link 2]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E5%8D%95%E5%85%83/8727749
[Link 3]: https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0/715313
[Link 4]: https://baike.baidu.com/item/%20%E6%8C%87%E9%92%88/2878304
[Link 5]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8/1582924
[Link 6]: https://baike.baidu.com/item/%E5%9C%B0%E5%9D%80/80420
[Link 7]: https://baike.baidu.com/item/%E5%AD%98%E5%82%A8%E5%8D%95%E5%85%83
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDcwNzMz_size_16_color_FFFFFF_t_70]: /images/20221120/fadfa25088924bc4932b05f08b23a06a.png