单链表逆序操作学习

前言

将单链表逆序，方法有三种：

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节点，完成逆序

代码实现

/**
 * Created by graymonkey on 18-3-8.
 * 链表节点
 */

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;
    }
}

/**
 * Created by graymonkey on 18-3-8.
 */

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);
    }
}

测试结果

参考文章

单链表逆序