算法之遞歸（3）- 鏈表操作

遞歸（2）嘗試了一個單鏈表的遍歷，同時又分析了如何添加自己的操作，是在遞歸調用之前，還是在遞歸調用之后。

今天，打算將問題深入一下，即添加相應的操作在遞歸的過程中。

（免責聲明：下面的解法純屬娛樂 ，另外，示例代碼未經編譯和調試，許多想法未經實踐驗證。）

查找鏈表當中倒數第N個節點。

解法一

逐層遞歸，遍歷到最后一個節點，并從返回的節點一次向后遞歸，遍歷N次，找到倒數第N個節點。

        private LNode targetNode = null;private LNode FindLastNthNode(LNode head, int index){if (head.Next == null){return head;}FindLastNthNode(head.Next, index);LNode tmpNode = head;while ((head.Next != null) && (index > 0)){head = head.Next;index--;}if (head.Next == null && index == 0){targetNode = tmpNode;return targetNode;}return targetNode;}

分析

1． 額外的全局性的輔助變量。

2． 時間復雜度為O(index * n)，n為鏈表的長度。

3． 性能開銷較大。

解法二（解法一的變形）

每當遍歷到當前節點，即再循環向后遍歷n個，如果節點遍歷到最后，并且index自減等于0，說明當前節點即為要找的倒數第n個。也就是說解法一是從后向前找，而解法二是從前向后找。

        private LNode targetNode2 = null;private LNode FindLastNthNode2(LNode head, int index){if (head.Next == null)return head;LNode tmpNode = head;while (head != null && index >= 0){head = head.Next;index--;}if (head == null && index == 0){targetNode2 = tmpNode;return targetNode2;}return targetNode2;}

分析：與解法一一樣。

解法三

定義一個全局變量，用來計數，當遞歸從最后一個節點返回時，計數器減減，當等于0時，這個節點即是要找的倒數第N個節點。

        private int counter = 0;private LNode targetNode2;private LNode FindLastNthNode2(LNode head, int index){if (head.Next == null){counter = index;return head;}FindLastNthNode2(head.Next, index);counter--;if (counter == 0){targetNode2 = head;return targetNode2;}return targetNode2;}

分析

1． 兩個輔助變量。

2． 時間復雜度為O(n)。

3． 多余的index，累贅的counter。

?

======= 后記 =======

其實以上幾個解決方案個人覺得都不夠perfect。

像類似于鏈表這樣的操作，基本就是兩指針。

于是我重新給了一個方案如下。

（該段代碼已經編譯、運行及測試通過）

?

解法四：

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication17
{class Program{static void Main(string[] args){Node head = new Node(){Data = "Head"};Node lucas = new Node(){Data = "Lucas"};Node bill = new Node(){Data = "Bill"};Node steve = new Node(){Data = "Steve"};Node anders = new Node(){Data = "Anders"};Node jordan = new Node(){Data = "Jordan"};head.Next = lucas;lucas.Next = bill;bill.Next = steve;steve.Next = anders;anders.Next = jordan;Program p = new Program();Node resultNode = p.FindLastNthNode(head, 2);Console.WriteLine(resultNode.Data);Console.ReadLine();}private Node FindLastNthNode(Node node, int n){if(node == null){return node;}if(n <= 0){throw new ArgumentException("n");}Node node1 = node;Node node2 = node;return this.InternalFindLastNthNode(node1, node2, n);}private Node InternalFindLastNthNode(Node node1, Node node2, int n){if(node1 == null){return node2;}if(n == 0){return this.InternalFindLastNthNode(node1.Next, node2.Next, 0);}return this.InternalFindLastNthNode(node1.Next, node2, --n);}}public class Node{public string Data { get; set; }public Node Next { get; set; }}
}

?

Best Regards,

Lucas Luo

轉載于:https://www.cnblogs.com/lucasluo/archive/2012/07/31/2617417.html

總結

以上是生活随笔為你收集整理的算法之递归（3）- 链表操作的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。