數(shù)據(jù)結(jié)構(gòu)之鏈表及其棧和隊(duì)列的實(shí)現(xiàn)

鏈表的基本操作

定義

class Node{
  Item item;//表示任意的數(shù)據(jù)類(lèi)型
  Node next;//指向下一個(gè)節(jié)點(diǎn)的引用
}

從鏈表頭部插入元素

Node oldFirst = first;//oldFirst指向原來(lái)的頭結(jié)點(diǎn)
first = new Node();
first.item = item;
first.next = oldFirst;

從鏈表頭部刪除元素

first = first.next; //first指向first.next即可

從鏈表尾部插入元素

Node oldLast = last;
last = new Node();
last.item = item;
oldLast.next = last;

從中間插入和刪除結(jié)點(diǎn)

Node first = new Node();
Node third = new Node();
first.next = third;
//在first和second之間插入second
Node second = new Node();
first.next = second;
second.next = third;
//刪除second結(jié)點(diǎn)(刪除結(jié)點(diǎn)必須知道前一個(gè)結(jié)點(diǎn))
first.next = third;

棧和對(duì)列的實(shí)現(xiàn)

棧的實(shí)現(xiàn)

使用數(shù)組實(shí)現(xiàn)棧

public class ArrayStack<Item> implements Iterable<Item>{

    //初始化數(shù)組的大小
    private Item[] arr = (Item[])new Object[5];
    private int N == 0;
    
    public int size(){
        return N;
    }
    
    public boolean isEmpty(){
        return N == 0 ? true : false; 
    }
    
    public void push(Item item){
        if(N == arr.length){
            resize(2*N);
        }
        arr[N++] = item;
    }
    
    public Item pop(){
        Item item = arr[--N];
        arr[N] = null;
        if(N > 0 && N == arr.length/4){
            resize(2*N);
        }
        return item;
    }
    //動(dòng)態(tài)調(diào)整數(shù)組大小
    public void resize(int capacity){
        Item[] temp = (Item[])new Object[capacity];
        for(int i = 0; i < N; i++){
           temp[i] = arr[i];
        }
        arr = temp;
    }
    
    //實(shí)現(xiàn)迭代器功能齐佳,可以使用foreach語(yǔ)句
    public Iterator<Item> iterator(){
        return new ArrayReverseIterator();
    }
    
    private class ArrayReverseIterator implements Iterator<Item>{
        private int index = N;
        public boolean hasNext(){
            return N > 0 ? true : false;
        }
        
        public Item next(){
            return arr[--N];
        }
    }
}

使用鏈表實(shí)現(xiàn)棧

public class NodeStack<Item> implements Iterable<Item> {

    private class Node{
        Item item;
        Node next;
    }

    private Node first;
    private int N = 0;

    public void push(Item item){
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }

    public Item pop(){
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }

    public boolean isEmpty(){
        return N == 0;
    }

    public int size(){
        return N;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ListIterator();
    }


    private class ListIterator implements Iterator<Item>{

        private Node current = first;

        @Override
        public boolean hasNext() {
            return current != null;
        }

        @Override
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }

}

隊(duì)列的實(shí)現(xiàn)

public class Queue<Item> implements Iterable<Item>{
    
    private class Node{
        Item item;
        Node next;
    }
    
    Node first;
    Node last;
    private int N = 0;
    
    public boolean isEmpty(){
        return N == 0;
    }
    
    public int size(){
        return N;
    }
    
    public void enqueue(Item item){
        Node oldLast = last;
        last = new Node();
        last.item = item;
        if(isEmpty()){
            first = last;
        }else{
            oldLast.next = last;
        }
        N++;
    }
    
    public Item dequeue(){
        Item item = first.item;
        first = first.next;
        if(isEmpty()){
            last = null;
        }
        N--;
        return item;
    }
    
    public Iterator<Item> iterator(){
       return new QueueIterator();
    }
    
    private class QueueIterator implements Iterator<Item>{
        
        private Node current = first;
        
        public boolean hasNext(){
            return current != null;
        }
        
        public Item next(){
            Item item = current.item;
            current = current.next;
            return item;
        }
        
    }
    
}

鏈表練習(xí)題目

1.有一個(gè)整數(shù)val留晚,如何在節(jié)點(diǎn)值有序的環(huán)形鏈表中插入一個(gè)節(jié)點(diǎn)值為val的節(jié)點(diǎn),并且保證這個(gè)環(huán)形單鏈表依然有序.給定鏈表的信息吼蚁,及元素的值A(chǔ)及對(duì)應(yīng)的nxt指向的元素編號(hào)同時(shí)給定val岳枷,請(qǐng)構(gòu)造出這個(gè)環(huán)形鏈表,并插入該值。

class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
      this.val = val;
    }
}
public ListNode insert(int[] A, int[] next, int val){
    
    if(A == null || A.length == 0){
        ListNode node = new ListNode(val);
        return node;
    }
    ListNode head = new ListNode(A[0]);
    ListNode point = head;
    ListNode current = null;
    //通過(guò)數(shù)組構(gòu)造鏈表
    for(int i = 0; i < next.length - 1; i++){
        current = new ListNode(A[next[i]]);
        ponit.next = current;
        point = current;
    }
    
    
    if(val < head.val){
        ListNode node = new ListNode(val);
        node.next = head;
        head = node;
        return head;
    }
    
    if(val > current.val){
       ListNode node = new ListNode(val);
       current.next = node;
       return head;
    }
    
    ListNode p1 = head;
    ListNode p2 = head.next;
    while(p1 != null && p2 != null){
        if(p1.val <= val && val <= p2.val){
            ListNode node = new ListNode(val);
            p1.next = node;
            node.next = p2;
            return head;
        }else{
            p1 = p1.next;
            p2 = p2.next;
        }
    }
    
    return head;
    
    
}

2.實(shí)現(xiàn)一個(gè)算法跺株,刪除單向鏈表中間的某個(gè)結(jié)點(diǎn),假定你只能訪問(wèn)該結(jié)點(diǎn)脖卖。給定帶刪除的節(jié)點(diǎn)乒省,請(qǐng)執(zhí)行刪除操作,若該節(jié)點(diǎn)為尾節(jié)點(diǎn)畦木,返回false袖扛,否則返回true.

public boolean remove(ListNode pNode){
        if(pNode.next == null){
            return false;
        }
        pNode.val = pNode.next.val;
        pNode.next = pNode.next.next;
        return true;
}

3.對(duì)于一個(gè)鏈表,我們需要用一個(gè)特定閾值完成對(duì)它的分化十籍,使得小于等于這個(gè)值的結(jié)點(diǎn)移到前面蛆封,大于該值的結(jié)點(diǎn)在后面,同時(shí)保證兩類(lèi)結(jié)點(diǎn)內(nèi)部的位置關(guān)系不變勾栗。給定一個(gè)鏈表的頭結(jié)點(diǎn)head惨篱,同時(shí)給定閾值val,請(qǐng)返回一個(gè)鏈表围俘,使小于等于它的結(jié)點(diǎn)在前砸讳,大于等于它的在后,保證結(jié)點(diǎn)值不重復(fù)界牡。

public ListNode listDivide(ListNode head,int val){

    public ListNode head_1 = null;
    public ListNode tail_1 = null;
    public ListNode head_2 = null;
    public ListNode tail_2 = null;
    public ListNode next = null;
    
    while(head != null){
       next = head.next;
       head.next = null;
       if(head.val <= val){
          ListNode oldTail_1 = tail_1;
          tail_1 = head;
          if(head_1 == null){
            head_1 = tail_1;
          }else{
            oldtail_1.next = tail_1;
          }
       }else if(head.val > val){
          ListNode oldTail_2 = tail_2;
          tail_2 = head;
          if(head_2 == null){
             head_2 = tail_2;
          }else{
             oldTail_2.next = tail_2;
          }
       }
       head = next;
    }
    
    if(tail_1 != null){
      tail_1.next = head_2;
    }
    
    return head_1 != null ? head_1 : head_2; 
    
}

4.有一個(gè)單鏈表绣夺,請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法,使得每K個(gè)節(jié)點(diǎn)之間逆序欢揖,如果最后不夠K個(gè)節(jié)點(diǎn)一組陶耍,則不調(diào)整最后幾個(gè)節(jié)點(diǎn)。例如鏈表1->2->3->4->5->6->7->8->null她混,K=3這個(gè)例子烈钞。調(diào)整后為,3->2->1->6->5->4->7->8->null坤按。因?yàn)镵==3毯欣,所以每三個(gè)節(jié)點(diǎn)之間逆序,但其中的7臭脓,8不調(diào)整酗钞,因?yàn)橹挥袃蓚€(gè)節(jié)點(diǎn)不夠一組。

public ListNode inverse(ListNode head,int k){
    if(head == null || head.next == null || k < 2){
        return head;
    }
    ListNode pre = null;
    ListNode current = head;
    ListNode start = null;
    ListNode next = null;
    int count = 1;
    while(current != null){
        next = current.next;
        if(count == 3){
            start = pre == null ? head : pre.next;
            head = pre == null ? current : head;
            reverse(pre,start,current,next);
            pre = start;
            count = 0;
        }
        count++;
        current = next;
    }
    return head;
    
}

//先逆序k個(gè)節(jié)點(diǎn)
public void reverse(ListNode left,ListNode start,ListNode end,ListNode right){
    ListNode current = start.next;
    ListNode point = start;
    ListNode next = null;
    while(current != right){
        next = current.next;
        current.next = point;
        point = current;
        current = next;
    }
    if(left != null){
        left.next = end;
    }
    start.next = right;
}



5.如何判斷一個(gè)單鏈表是否有環(huán)?有環(huán)的話返回進(jìn)入環(huán)的第一個(gè)節(jié)點(diǎn)的值砚作,無(wú)環(huán)的話返回-1窘奏。

 public int chkLoop(ListNode head, int adjust) {
        if(head == null){
            return -1;
        }
        boolean isCircle = false;
        ListNode fast = head;
        ListNode slow = head;
        while(slow != null && fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                isCircle = true;
                break;
            }
        }
        if(!isCircle){
            return -1;
        }
        fast = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow.val;

    }

6.現(xiàn)在有兩個(gè)無(wú)環(huán)單鏈表,若兩個(gè)鏈表的長(zhǎng)度分別為m和n葫录,請(qǐng)?jiān)O(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n + m)着裹, 額外空間復(fù)雜度為O(1)的算法,判斷這兩個(gè)鏈表是否相交米同。

public boolean chkIntersect(ListNode headA, ListNode headB) {

        if(headA == null || headB == null){
            return false;
        }
        boolean isIntersect = false;
        int lenA = 0;
        ListNode p1 = headA;
        while(p1 != null){
            p1 = p1.next;
            lenA++;
        }
        int lenB = 0;
        ListNode p2 = headB;
        while(p2 != null){
            p2 = p2.next;
            lenB++;
        }
        if(lenA >= lenB){
            isIntersect = isCrossing(headA,headB,lenA - lenB);
        }else{
            isIntersect = isCrossing(headB,headA,lenB - lenA);
        }
        return isIntersect;
    }

public boolean isCrossing(ListNode headA, ListNode headB, int num){
        ListNode curA = headA;
        boolean isCross = false;
        while(num != 0){
            curA = curA.next;
            num--;
        }
        ListNode curB = headB;
        while(curA != null && curB != null){
            if(curA == curB){
                isCross = true;
                break;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return isCross;
    }

7.如何判斷兩個(gè)有環(huán)單鏈表是否相交骇扇?相交的話返回第一個(gè)相交的節(jié)點(diǎn),不想交的話返回空面粮。

public boolean chkInter(ListNode head1, ListNode head2, int adjust0, int adjust1) {

        if(head1 == null || head2 == null){
            return false;
        }

        ListNode p1 = insert(head1);
        ListNode p2 = insert(head2);
        //入環(huán)節(jié)點(diǎn)相交
        if(p1 == p2){
            return true;
        }
        //環(huán)中相交
        ListNode start1 = p1.next;
        while(start1 != p1){
            if(start1 == p2){
                return true;
            }
            start1 = start1.next;
        }
        return false;
    }

    //入環(huán)節(jié)點(diǎn)
    public ListNode insert(ListNode head){
        ListNode slow = head;
        ListNode fast = head;
        while(slow != null && fast != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                break;
            }
        }
        fast = head;
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末少孝,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子熬苍,更是在濱河造成了極大的恐慌稍走,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件冷溃,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡梦裂,警方通過(guò)查閱死者的電腦和手機(jī)似枕,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)年柠,“玉大人凿歼,你說(shuō)我怎么就攤上這事∪吆蓿” “怎么了答憔?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)掀抹。 經(jīng)常有香客問(wèn)我虐拓,道長(zhǎng),這世上最難降的妖魔是什么傲武? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任蓉驹,我火速辦了婚禮,結(jié)果婚禮上揪利,老公的妹妹穿的比我還像新娘态兴。我一直安慰自己,他們只是感情好疟位,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布瞻润。 她就那樣靜靜地躺著,像睡著了一般。 火紅的嫁衣襯著肌膚如雪绍撞。 梳的紋絲不亂的頭發(fā)上正勒,一...
    開(kāi)封第一講書(shū)人閱讀 52,736評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音楚午,去河邊找鬼昭齐。 笑死,一個(gè)胖子當(dāng)著我的面吹牛矾柜,可吹牛的內(nèi)容都是我干的阱驾。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼怪蔑,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼里覆!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起缆瓣,我...
    開(kāi)封第一講書(shū)人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤喧枷,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后弓坞,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體隧甚,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年渡冻,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了戚扳。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡族吻,死狀恐怖帽借,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情超歌,我是刑警寧澤砍艾,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布,位于F島的核電站巍举,受9級(jí)特大地震影響脆荷,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜懊悯,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一简烘、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧定枷,春花似錦孤澎、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)退子。三九已至,卻和暖如春型将,著一層夾襖步出監(jiān)牢的瞬間寂祥,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工七兜, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留丸凭,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓腕铸,卻偏偏與公主長(zhǎng)得像惜犀,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子狠裹,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361

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