频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
实现单链表的反转
2017-02-18 09:12:00         来源:陶程的博客  
收藏   我要投稿

实现单链表的反转:为了正确反转一个链表,需要调整指针的指向。举例说明,例如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/实现链表的反转。

点击复制链接 与好友分享!回本站首页
上一篇:策略模式之把会变化的部分取出并封装起来
下一篇:找出单链表中的倒数第k个元素
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站