首页 > 程序开发 > 软件开发 > 其他 >

实现单链表的反转

2017-02-18

实现单链表的反转:为了正确反转一个链表,需要调整指针的指向。举例说明,例如i,m,n是三个相邻的结点,假设经过若干步操作,已经把结点i之前的指针调整完毕,这些结点的next指针都指向前面一个结点。

实现单链表的反转:为了正确反转一个链表,需要调整指针的指向。举例说明,例如i,m,n是三个相邻的结点,假设经过若干步操作,已经把结点i之前的指针调整完毕,这些结点的next指针都指向前面一个结点。

现在遍历到结点m,当然需要调整结点的next指针,让它指向结点i,但需要注意的是,一旦调整了指针的指向,链表就断开了。

因为已经没有指针指向结点n,没有办法再遍历到结点n了,所以为了避免指针断开,需要在调整m的next之前要把n保存下来。接下来试着找到反转后链表的头结点。不难分析出翻转后链表的头结点是原始链表的尾结点,即next为空指针的结点。

实现代码如下:

/**
 * 两种方式实现单链表的反转
 * @author dream
 *
 */
public class ReverseSingleList {

    /**
     * 递归,在反转当前结点之前先反转后续结点
     * @param node
     * @return
     */
    public static Node reverse(Node head){
        if(head == null || head.getNextNode() == null){
            return head;
        }
        Node reversedHead = reverse(head.getNextNode());
        head.getNextNode().setNextNode(head);
        head.setNextNode(null);
        return reversedHead;
    }

    /**
     * 遍历,将当前结点的下一个结点缓存后更改当前结点
     */
    public static Node reverse2(Node head){
        if(head == null){
            return head;
        }
        Node pre = head;
        Node cur = head.getNextNode();
        Node next;
        while (cur != null) {
            next = cur.getNextNode();
            cur.setNextNode(pre);
            pre = cur;
            cur = next;
        }
        //将原链表的头结点的下一个结点置为null,再将反转后的头结点赋给head
        head.setNextNode(null);
        head = pre;
        return head;
    }
}

Github源码地址

https://github.com/GeniusVJR/Algorithm-and-Data-Structure/tree/master/实现链表的反转。

相关文章
最新文章
热点推荐