首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >剑指Offer面试题:15.反转链表

剑指Offer面试题:15.反转链表

作者头像
Edison Zhou
发布2018-08-20 16:13:20
2870
发布2018-08-20 16:13:20
举报
文章被收录于专栏:EdisonTalkEdisonTalk

一、题目:反转链表

题目:定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

  链表结点定义如下,这里使用的是C#描述:

    public class Node
    {
        public int Data { get; set; }
        // 指向后一个节点
        public Node Next { get; set; }

        public Node(int data)
        {
            this.Data = data;
        }

        public Node(int data, Node next)
        {
            this.Data = data;
            this.Next = next;
        }
    }

二、解题思路

2.1 借助外部空间的解法一

  由于题目并没有要求必须原地反转,因此可以借助外部空间实现。这里可以将单链表储存为数组,然后按照数组的索引逆序进行反转。但是,此方式比较浪费空间,而且需要两次遍历,效率不占优势

  依据上面的思路,我们可以写出以下代码:

    public static Node ReverseList1(Node head)
    {
        if(head == null)
        {
            return null;
        }

        List<Node> nodeList = new List<Node>();
        while (head != null)
        {
            nodeList.Add(head);
            head = head.Next;
        }

        int startIndex = nodeList.Count - 1;
        for (int i = startIndex; i >= 0; i--)
        {
            Node node = nodeList[i];
            if (i == 0)
            {
                node.Next = null;
            }
            else
            {
                node.Next = nodeList[i - 1];
            }
        }
        // 现在头结点是原来的尾节点
        head = nodeList[startIndex];
        return head;
    }

2.2 使用三个指针的高效解法二

  定义3个指针,分别指向当前遍历到的结点、它的前一个结点及后一个结点。在遍历过程中,首先记录当前节点的后一个节点,然后将当前节点的后一个节点指向前一个节点,其次前一个节点再指向当前节点,最后再将当前节点指向最初记录的后一个节点,如此反复,直到当前节点的后一个节点为NULL时,则代表当前节点时反转后的头结点了。

  整个过程只需遍历链表一次,效率提高不少,且需要的外部空间也较第一种方法要少很多,实现代码如下:

    public static Node ReverseList2(Node head)
    {
        if (head == null)
        {
            return null;
        }

        Node reverseHead = null;
        // 指针1:当前节点
        Node currentNode = head;
        // 指针2:当前节点的前一个节点
        Node prevNode = null;

        while(currentNode != null)
        {
            // 指针3:当前节点的后一个节点
            Node nextNode = currentNode.Next;
            if(nextNode == null)
            {
                reverseHead = currentNode;
            }
            // 将当前节点的后一个节点指向前一个节点
            currentNode.Next = prevNode;
            // 将前一个节点指向当前节点
            prevNode = currentNode;
            // 将当前节点指向后一个节点
            currentNode = nextNode;
        }

        return reverseHead;
    }

三、单元测试

3.1 测试用例

  (1)为了方便对比,封装了一个用于将链表所有元素输出为字符串的方法GetNodeString()

    // 辅助方法:生成链表元素的字符串用于对比
    public string GetNodeString(Node head)
    {
        if (head == null)
        {
            return null;
        }

        StringBuilder sbResult = new StringBuilder();
        Node temp = head;
        while (temp != null)
        {
            sbResult.Append(temp.Data.ToString());
            temp = temp.Next;
        }

        return sbResult.ToString();
    } 

  (2)功能测试、特殊输入测试

    // 01.输入的链表有多个结点
    [TestMethod]
    public void ReverseTest1()
    {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node1.Next = node2;
        node2.Next = node3;
        node3.Next = node4;
        node4.Next = node5;

        Node newHead = ListHelper.ReverseList2(node1);
        Assert.AreEqual(GetNodeString(newHead), "54321");
    }

    // 02.输入的链表只有一个结点
    [TestMethod]
    public void ReverseTest2()
    {
        Node node1 = new Node(1);

        Node newHead = ListHelper.ReverseList2(node1);
        Assert.AreEqual(GetNodeString(newHead), "1");
    }

    // 03.输入NULL
    [TestMethod]
    public void ReverseTest3()
    {
        Node newHead = ListHelper.ReverseList2(null);
        Assert.AreEqual(GetNodeString(newHead), null);
    } 

3.2 测试结果

  (1)测试通过情况

  (2)代码覆盖率

作者:周旭龙

出处:http://edisonchou.cnblogs.com

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文链接。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015-08-29 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、题目:反转链表
  • 二、解题思路
    • 2.1 借助外部空间的解法一
      • 2.2 使用三个指针的高效解法二
      • 三、单元测试
        • 3.1 测试用例
          • 3.2 测试结果
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档