問題

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

知識點

快慢指針、鏈表反轉

實現思路

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

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

復雜度為O(n)的方法

1. 如果使用單鏈表存儲，那么第一步需要找到鏈表的中間節點，這一步需要用到快慢指針
2. 第二步需要將單鏈表的后半部分進行反轉，單鏈表的反轉

代碼

定義鏈表結構

/**
 * 單鏈表的節點類
 *
 * @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;

    /**
     * 從尾部添加一個節點
     *
     * @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;
    }

    /**
     * 打印鏈表內容
     *
     * @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();
    }

}

從指定的位置反轉單鏈表

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


    //反轉尾部的鏈表進行比較
    SinglyLinedNode cursor = new SinglyLinedNode(null, singlyLinkedList.head);
    int temp = 0;
    //begin作為一個偽頭結點
    SinglyLinedNode begin = new SinglyLinedNode(null, singlyLinkedList.head);
    if (index == 0) {
        singlyLinkedList.head = begin;
    }
    //mid作為截取隊列的的首個節點
    SinglyLinedNode mid = null;
    //end是需要進行頭插的節點
    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;
        }

        //反轉半個鏈表，就地逆置法
        if (temp > index && end != null) {
            //將需要逆序的元素，直接作為頭結點的后繼節點
            mid.next = end.next;
            end.next = begin.next;
            begin.next = end;
            //保持遍歷的順序，將游標往后移動
            cursor = mid;
            //如果還有需要進行頭插的元素，則end指針需要往后移動一下
            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;
}

最終方法

/**
 * 單鏈表結構判斷字符串是否是回文字符串
 * 一般方法 復雜度為O(n2)
 * 1. 如果字符串存儲在數組中，那么只需要判斷第一個和最后一個這么一一對應下去，判斷字符是否相同，還是比較簡單的。
 * 2. 如果單鏈表中存儲也參照這種方法，那么可以定義兩個指針，一個初始指向頭部，一個初始指向尾部，后續依次一個向后指一個依次向前指。這樣也能判斷是否是回文字符串。但是對于單鏈表，查找前繼節點，需要遍歷鏈表，所以復雜度是O(n2)
 * 復雜度為O(n)的方法
 * 1. 如果使用單鏈表存儲，那么第一步需要找到鏈表的中間節點，這一步需要用到快慢指針
 * 2. 第二步需要將單鏈表的后半部分進行反轉，單鏈表的反轉
 *
 * @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());

        //查找鏈表的中間節點的下標 快慢指針
        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("從中間反轉后原鏈表：" + singlyLinkedList.getString());
        System.out.println("反轉后截取的鏈表：" + singlyLinkedList1.getString());
        //定義兩個指針挨個比較
        System.out.println("需要比較的節點數量中間數為"+(index%2==0?"偶數則-1":"奇數則不變")+"："+(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判斷結果："+testStr+"不是回文字符串");
                return;
            }

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


    }


    


    /**
     * 將字符串轉換為單鏈表
     *
     * @param targetStr 目標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;

    }

}