問(wèn)題

如果字符串存儲(chǔ)在單鏈表中，怎么快速判斷這個(gè)字符串是否是回文字符串？

知識(shí)點(diǎn)

快慢指針、鏈表反轉(zhuǎn)

實(shí)現(xiàn)思路

一般方法 復(fù)雜度為O(n2)

1. 如果字符串存儲(chǔ)在數(shù)組中，那么只需要判斷第一個(gè)和最后一個(gè)這么一一對(duì)應(yīng)下去，判斷字符是否相同，還是比較簡(jiǎn)單的。
2. 如果單鏈表中存儲(chǔ)也參照這種方法，那么可以定義兩個(gè)指針，一個(gè)初始指向頭部，一個(gè)初始指向尾部，后續(xù)依次一個(gè)向后指一個(gè)依次向前指。這樣也能判斷是否是回文字符串。但是對(duì)于單鏈表，查找前繼節(jié)點(diǎn)，需要遍歷鏈表，所以復(fù)雜度是O(n2)

復(fù)雜度為O(n)的方法

1. 如果使用單鏈表存儲(chǔ)，那么第一步需要找到鏈表的中間節(jié)點(diǎn)，這一步需要用到快慢指針
2. 第二步需要將單鏈表的后半部分進(jìn)行反轉(zhuǎn)，單鏈表的反轉(zhuǎn)

代碼

定義鏈表結(jié)構(gòu)

/**
 * 單鏈表的節(jié)點(diǎn)類
 *
 * @author StoneYu
 * @date 2022/09/25
 */
@Data
@AllArgsConstructor
public class SinglyLinedNode<T> {
    T data;
    SinglyLinedNode<T> next;

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public SinglyLinedNode<T> getNext() {
        return next;
    }

    public void setNext(SinglyLinedNode<T> next) {
        this.next = next;
    }
}

@Data
public class SinglyLinkedList<T> {

    /**
     * 單鏈表的頭指針
     */
    SinglyLinedNode<T> head;

    /**
     * 從尾部添加一個(gè)節(jié)點(diǎn)
     *
     * @param t t
     */
    public void add(SinglyLinedNode<T> t) {
        if (t == null) {
            return;
        }
        if (head == null) {
            head = t;
            return;
        }

        SinglyLinedNode<T> couser = head;
        while (couser.next != null) {
            couser = couser.next;
        }
        couser.next = t;
    }

    /**
     * 打印鏈表內(nèi)容
     *
     * @return {@link String}
     */
    public String getString() {
        if (head == null) {
            return null;
        }
        StringBuilder stringBuilder = new StringBuilder();

        SinglyLinedNode<T> couser = head;
        stringBuilder.append("鏈表：" + (couser.getData()==null?"null":couser.getData()));
        while (couser.next != null) {
            couser = couser.next;
            stringBuilder.append("->" + (couser.getData()==null?"null":couser.getData()));
        }
        return stringBuilder.toString();
    }

}

從指定的位置反轉(zhuǎn)單鏈表

/**
* 從第 index+1 的元素開(kāi)始反轉(zhuǎn),0反轉(zhuǎn)整個(gè)鏈表
*
* @param singlyLinkedList 單鏈表
* @param index            下標(biāo) >0
*/
static SinglyLinkedList reverseALinkedList(SinglyLinkedList singlyLinkedList, int index) {
    //空、或者只有1個(gè)元素
    if (singlyLinkedList.head == null || singlyLinkedList.head.next == null) {
        return singlyLinkedList;
    }
    if (index <= 0) {
        index = 0;
    }


    //反轉(zhuǎn)尾部的鏈表進(jìn)行比較
    SinglyLinedNode cursor = new SinglyLinedNode(null, singlyLinkedList.head);
    int temp = 0;
    //begin作為一個(gè)偽頭結(jié)點(diǎn)
    SinglyLinedNode begin = new SinglyLinedNode(null, singlyLinkedList.head);
    if (index == 0) {
        singlyLinkedList.head = begin;
    }
    //mid作為截取隊(duì)列的的首個(gè)節(jié)點(diǎn)
    SinglyLinedNode mid = null;
    //end是需要進(jìn)行頭插的節(jié)點(diǎn)
    SinglyLinedNode end = null;

    while (cursor.next != null) {
        //遍歷鏈表
        cursor = cursor.next;
        temp++;

        if (temp == index) {
            begin = cursor;
        }
        if (temp - 1 == index) {
            mid = cursor;
            end = cursor.next;
        }

        //反轉(zhuǎn)半個(gè)鏈表，就地逆置法
        if (temp > index && end != null) {
            //將需要逆序的元素，直接作為頭結(jié)點(diǎn)的后繼節(jié)點(diǎn)
            mid.next = end.next;
            end.next = begin.next;
            begin.next = end;
            //保持遍歷的順序，將游標(biāo)往后移動(dòng)
            cursor = mid;
            //如果還有需要進(jìn)行頭插的元素，則end指針需要往后移動(dòng)一下
            if (mid.next != null) {
                end = mid.next;
            }
        }
    }
    if (index == 0) {
        singlyLinkedList.head = begin.next;
    }

    SinglyLinkedList<Object> objectSinglyLinkedList = new SinglyLinkedList<>();
    objectSinglyLinkedList.setHead(begin.next);

    return objectSinglyLinkedList;
}

最終方法

/**
 * 單鏈表結(jié)構(gòu)判斷字符串是否是回文字符串
 * 一般方法 復(fù)雜度為O(n2)
 * 1. 如果字符串存儲(chǔ)在數(shù)組中，那么只需要判斷第一個(gè)和最后一個(gè)這么一一對(duì)應(yīng)下去，判斷字符是否相同，還是比較簡(jiǎn)單的。
 * 2. 如果單鏈表中存儲(chǔ)也參照這種方法，那么可以定義兩個(gè)指針，一個(gè)初始指向頭部，一個(gè)初始指向尾部，后續(xù)依次一個(gè)向后指一個(gè)依次向前指。這樣也能判斷是否是回文字符串。但是對(duì)于單鏈表，查找前繼節(jié)點(diǎn)，需要遍歷鏈表，所以復(fù)雜度是O(n2)
 * 復(fù)雜度為O(n)的方法
 * 1. 如果使用單鏈表存儲(chǔ)，那么第一步需要找到鏈表的中間節(jié)點(diǎn)，這一步需要用到快慢指針
 * 2. 第二步需要將單鏈表的后半部分進(jìn)行反轉(zhuǎn)，單鏈表的反轉(zhuǎn)
 *
 * @author StoneYu
 * @date 2022/09/25
 */
public class TestHuiWenZiFuChuan {

    public static void main(String[] args) {
        String testStr = "1";
        SinglyLinkedList<Character> singlyLinkedList = transStringToLinkedList(testStr);
        System.out.println(singlyLinkedList.getString());

        //查找鏈表的中間節(jié)點(diǎn)的下標(biāo) 快慢指針
        SinglyLinedNode slow = singlyLinkedList.head;
        SinglyLinedNode quick = singlyLinkedList.head;
        int index = 1;
        while (quick.next != null) {
            slow = slow.next;
            quick = quick.next;
            if (quick.next == null) {
                break;
            }
            quick = quick.next;
            index++;
        }
        SinglyLinkedList singlyLinkedList1 = reverseALinkedList(singlyLinkedList, index);
        System.out.println("中間位置為:"+index);
        System.out.println("從中間反轉(zhuǎn)后原鏈表：" + singlyLinkedList.getString());
        System.out.println("反轉(zhuǎn)后截取的鏈表：" + singlyLinkedList1.getString());
        //定義兩個(gè)指針挨個(gè)比較
        System.out.println("需要比較的節(jié)點(diǎn)數(shù)量中間數(shù)為"+(index%2==0?"偶數(shù)則-1":"奇數(shù)則不變")+"："+(index%2==0?index-1:index));
        int needConpare=index%2==0?index-1:index;

        int hasCompare=0;
        SinglyLinedNode<Character> cursor1=new SinglyLinedNode(null,singlyLinkedList.head);
        SinglyLinedNode<Character> cursor2=new SinglyLinedNode(null,singlyLinkedList1.head);
        for (int i = 0; i <needConpare; i++) {
            Character data1 = cursor1.next.data;
            Character data = cursor2.next.data;
            if (!data1.equals(data)){
                System.out.println("\n\n判斷結(jié)果："+testStr+"不是回文字符串");
                return;
            }

        }
        System.out.println("\n\n判斷結(jié)果："+testStr+"是回文字符串");


    }


    


    /**
     * 將字符串轉(zhuǎn)換為單鏈表
     *
     * @param targetStr 目標(biāo)str
     * @return {@link SinglyLinkedList}<{@link Character}>
     */
    static SinglyLinkedList<Character> transStringToLinkedList(String targetStr) {
        if (targetStr == null || targetStr.trim().equals("")) {
            return null;
        }
        char[] chars = targetStr.toCharArray();
        SinglyLinkedList<Character> characterSinglyLinkedList = new SinglyLinkedList<>();
        for (Character aChar : chars) {
            characterSinglyLinkedList.add(new SinglyLinedNode<>(aChar, null));
        }
        return characterSinglyLinkedList;

    }

}