单链表逆序操作学习

  • Post author:
  • Post category:其他


前言

将单链表逆序,方法有三种:

  1. 遍历链表,将每个节点的内容存入一个数组中,然后逆序输出数组,并重新构造一个链表
  2. 使用栈来逆序输出,原理与1相似,出栈的时候也需要重新构造一个新链表
  3. 直接将链表逆序然后输出

    其中,前面2种方法原理相似,也比较好理解,但是这样会耗费额外的内存空间;第三种方法则不需要额外的内存空间,便可实现单链表的逆序。

本文主要记录对第三种方法的操作原理。

原理

第三种方法主要通过三个指针来实现单链表的逆序, 初始状态如下图所示,prev为null,head指向链表的第一个节点(非头部节点),为方便描述,后面将head指针指向的节点称为head节点,next指向head的下一个节点。

初始状态

第一步:先将head节点的next指向prev,这相当于将head节点从灰色矩形框内的链表中分离。

第二步:将prev指向刚分离出来的head节点

第三步:将head、next指针分别右移一次指向下一个节点

经过以上步骤之后,此时的状态应该如下图所示:

第一轮操作结果

再按上面的步骤进行一轮,此时的结果应该如下图所示:

第二轮操作结果

如此反复,直到head指针为null,按本文例子,在进行第三轮操作后,head指针便为null,此时退出循环,结果应该如下图所示:

第三轮操作结果

仔细观察第三轮操作结果图,发现我们只需要再将链表头的next指向prev节点,即可完成单链表的逆序,整个过程并没有产生额外的空间分配。

整理链表头,完成逆序操作

经过上面的介绍,该方法的执行步骤总结如下:

  1. 先将head节点的next指向prev,这相当于将head节点从灰色矩形框内的链表中分离。
  2. 将prev指向刚分离出来的head节点
  3. 将head、next指针分别右移一次指向下一个节点
  4. 重复1-3步,直到head指针为null
  5. 设置链表头,将原链表头的next指向prev节点,完成逆序

代码实现

public class Node {
    private Integer mData;
    private Node mNext;

    public Integer getData() {
        return mData;
    }

    public void setData(Integer mData) {
        this.mData = mData;
    }

    public Node getNext() {
        return mNext;
    }

    public void setNext(Node mNext) {
        this.mNext = mNext;
    }
}

public class LinkedListUtils {
    /**
     * 构造单链表
     * @return
     */
    public static Node obtainLinkedList(){
        Node head = new Node();
        Node tail = head;
        for (int i =0;i<5;i++){
            Node node = new Node();
            node.setData(i);
            tail.setNext(node);
            tail = node;
        }
        printLinkedList(head);
        return head;
    }

    /***
     * 反向单链表
     * @param linkedList
     * @return
     */
    public static Node reverseLinkedList(Node linkedList){
        Node prev =null;
        Node head ;
        Node next ;
        //如果是空链表或者只有一个节点则无需反向
        if (linkedList.getNext() == null || linkedList.getNext().getNext() == null){
            return linkedList;
        }
        //从链表的第一个节点开始
        head = linkedList.getNext();
        while (head != null){
           //step3. 移动next指针
           next = head.getNext();
           //step1. 将头结点从链表中分离处理
           head.setNext(prev);
           //step2. 移动prev指针指向上步分离出来的节点
           prev=head;
           //step3. 移动head指针
           head = next;
        }
        //step5. 设置链表头
        linkedList.setNext(prev);
        printLinkedList(linkedList);
        return linkedList;

    }

    public static void printLinkedList(Node head){
        Node p =head;
        while (p !=null){
            Node next = p.getNext();
            if (next != null){
            Log.d("LinkedList data",next.getData()+"");
            }
            p=next;
        }
    }
}

测试代码:

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.layout);
        Node linkedList = LinkedListUtils.obtainLinkedList();
        Log.d("graymonkey","--------逆序后输出");
        LinkedListUtils.reverseLinkedList(linkedList);
    }
}



作者:GrayMonkey

链接:https://www.jianshu.com/p/43ff77f0da95

来源:简书

简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。