鏈表試題及解法

個(gè)人認(rèn)為,算法是程序員的內(nèi)功锌订,不管你是能把 Java 或是 C # 玩出花來,也是需要注意提升一下內(nèi)在修煉的画株。畢竟辆飘,只有深厚的內(nèi)功才能把招式發(fā)揮到極致。以下算法谓传,可能咋一看覺得很簡單蜈项,自己也能實(shí)現(xiàn),但是要知道能實(shí)現(xiàn)功能固然重要续挟,但算法的效率更值得研究紧卒。紙上得來終覺淺,相信如果你能把以下算法都親手實(shí)現(xiàn)一遍诗祸,必定會有收獲跑芳,至少我個(gè)人是這樣。

想要實(shí)現(xiàn)以下將介紹算法直颅,首先需要自己實(shí)現(xiàn)一個(gè) 鏈表博个,下面粘貼上我利用前插法寫的鏈表。

public class MyList {

    private Node first;
    
    public MyList(){
        
    }

    public class Node {
        Node next;
        int data;

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

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

    }

    public void add(int data) {
        first = add(first, data);
    }

    private Node add(Node x, int data) {
        if (x == null)
            return new Node(data);
        return new Node(x, data);
    }

    public Node getFirst() {
        return first;
    }

}

2.1 編寫代碼功偿,移除未排序鏈表中的重復(fù)結(jié)點(diǎn)盆佣。如果不能使用緩沖區(qū),又該怎么解決械荷?

// 借用臨時(shí)緩沖區(qū)的解法
    public static void deleteSame(MyList list) {
        MyList.Node current = list.getFirst();
        MyList.Node pre = null;
        Hashtable<Integer, Boolean> hashtable = new Hashtable<>();
        while (current != null) {
            if (hashtable.containsKey(current.data)) {
                pre.next = current.next;
            } else {
                hashtable.put(current.data, true);
                pre = current;
            }
            current = current.next;
        }
    }

    // 不借用臨時(shí)緩沖區(qū)

    public static void deleteSameTwo(MyList list) {
        MyList.Node current = list.getFirst();
        MyList.Node runner;
        while (current != null) {
            runner = current;
            while (runner.next != null) {
                if (runner.next.data == current.data) {
                    runner.next = runner.next.next;
                }
                runner = runner.next;
            }
            current = current.next;
        }
    }

2.2 實(shí)現(xiàn)一個(gè)算法共耍,找出單鏈表中倒數(shù)第 k 個(gè)結(jié)點(diǎn).

    // 只打印該元素,不返回該元素
    private static int findOne(MyList.Node node, int k) {
        if (node == null)
            return 0;
        int i = findOne(node.next, k) + 1;
        if (i == k)
            System.out.println(node.data);
        return i;
    }

    // 基于以上方法 利用 IntWrapper返回該元素
    private class IntWrapper {
        public int value = 0;
    }

    
    private static MyList.Node findTwo(MyList.Node node, int k, IntWrapper i) {
        if (node == null)
            return null;

        MyList.Node t = findTwo(node.next, k, i);
        i.value = i.value + 1;
        if (i.value == k) {
            return node;
        }
        return t;
    }

注意除了以上兩種算法吨瞎,還有一種方法痹兜,就是設(shè)置兩個(gè)指針,一個(gè)是快指針关拒,一個(gè)是慢指針佃蚜,先讓快指針向前移動∮褂椤k-1 次,也就是移動到 第⌒乘恪k 個(gè)元素熟尉,然后讓 慢指針開始移動,這樣的話當(dāng)快指針指到末尾的時(shí)候洲脂,慢指針指向的剛好是 倒數(shù)第〗锒k 個(gè)元素。


2.3 實(shí)現(xiàn)一個(gè)算法恐锦,刪除單向鏈表中間的某個(gè)結(jié)點(diǎn)往果,假定你只能訪問該結(jié)點(diǎn)。

private static void delete(Node root) {

        // 如果當(dāng)前節(jié)點(diǎn)為空或者當(dāng)前節(jié)點(diǎn)為尾節(jié)點(diǎn)的時(shí)候直接退出
        if (root == null || root.next == null) {
            return;
        }

        Node next = root.next;
        root.data = next.data;
        root.next = next.next;
    }

2.4 編寫代碼一铅,以給定值 x 為基準(zhǔn)將鏈表分割成兩部分陕贮,所有小于 x 的結(jié)點(diǎn)排在大于或等于 x 的節(jié)點(diǎn)之前。

public static Node divide(Node root, int x) {
        MyList mins = new MyList();
        MyList maxs = new MyList();

        while (root != null) {
            if (root.data < x) {
                mins.add(root.data);
            } else {
                maxs.add(root.data);
            }
            root = root.next;
        }

        Node minRoot = mins.getFirst();
        Node maxRoot = maxs.getFirst();

        if (minRoot == null) {
            return maxRoot;
        }
        Node temp = minRoot;
        while (minRoot.next != null)
            minRoot = minRoot.next;

        minRoot.next = maxRoot;
        return temp;
    }

2.5 給定兩個(gè)用鏈表表示的整數(shù)潘飘,每個(gè)節(jié)點(diǎn)包含一個(gè)數(shù)位肮之。這些數(shù)位是反向存放的,也就是個(gè)位排在鏈表首部卜录。編寫函數(shù)對兩個(gè)整數(shù)求和戈擒,并用鏈表形式返回結(jié)果。

public static Node addLists(Node n1, Node n2, int carry) {

        if (n1 == null && n2 == null && carry == 0) {
            return null;
        }

        Node result = new MyList().new Node();

        int value = carry;
        if (n1 != null) {
            value += n1.data;
        }
        if (n2 != null) {
            value += n2.data;
        }

        result.data = value % 10;

        Node more = addLists(n1 == null ? null : n1.next, n2 == null ? null : n2.next, value / 10);

        result.next = more;
        return result;

    }

2.6 編寫一個(gè)函數(shù)艰毒,檢查鏈表是否為回文筐高。

public static boolean isPalindrome(Node root) {

        Node fast = root;
        Node slow = root;

        Stack<Integer> stack = new Stack<>();

        while (fast != null && fast.next != null) {
            stack.push(slow.data);
            slow = slow.next;
            fast = fast.next.next;
        }

        // 說明有奇數(shù)個(gè)元素,跳過中間元素
        if (fast != null) {
            slow = slow.next;
        }

        while (slow != null) {
            int top = stack.pop().intValue();

            if (top != slow.data)
                return false;
            slow = slow.next;
        }
        return true;
}

以上代碼實(shí)現(xiàn)都是核心代碼丑瞧,需要完整代碼的 點(diǎn)擊此處

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末柑土,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子嗦篱,更是在濱河造成了極大的恐慌冰单,老刑警劉巖幌缝,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件灸促,死亡現(xiàn)場離奇詭異,居然都是意外死亡涵卵,警方通過查閱死者的電腦和手機(jī)浴栽,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來轿偎,“玉大人典鸡,你說我怎么就攤上這事』祷蓿” “怎么了萝玷?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵嫁乘,是天一觀的道長。 經(jīng)常有香客問我球碉,道長蜓斧,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任睁冬,我火速辦了婚禮挎春,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘豆拨。我一直安慰自己直奋,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布施禾。 她就那樣靜靜地躺著脚线,像睡著了一般。 火紅的嫁衣襯著肌膚如雪弥搞。 梳的紋絲不亂的頭發(fā)上殉挽,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天,我揣著相機(jī)與錄音拓巧,去河邊找鬼斯碌。 笑死,一個(gè)胖子當(dāng)著我的面吹牛肛度,可吹牛的內(nèi)容都是我干的傻唾。 我是一名探鬼主播,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼承耿,長吁一口氣:“原來是場噩夢啊……” “哼冠骄!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起加袋,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤凛辣,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后职烧,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體扁誓,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年蚀之,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了蝗敢。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,865評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡足删,死狀恐怖寿谴,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情失受,我是刑警寧澤讶泰,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布咏瑟,位于F島的核電站,受9級特大地震影響痪署,放射性物質(zhì)發(fā)生泄漏响蕴。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一惠桃、第九天 我趴在偏房一處隱蔽的房頂上張望浦夷。 院中可真熱鬧,春花似錦辜王、人聲如沸劈狐。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽肥缔。三九已至,卻和暖如春汹来,著一層夾襖步出監(jiān)牢的瞬間续膳,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工收班, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留坟岔,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓摔桦,卻偏偏與公主長得像社付,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個(gè)殘疾皇子邻耕,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容