【作业6_2】链表专题：回文链表-跟着帅地玩副业，开拓第二曲线PlayOffer

幽小皮永久会员 2024年4月8日下午8:04

“`
//快慢指针加递归
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null){
return true;
}
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode halfEnd = reverseList(slow.next);
while(head != null && halfEnd != null){
if(head.val != halfEnd.val){
return false;
}
head = head.next;
halfEnd = halfEnd.next;
}
return true;
}
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}

    ListNode newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;

}

}
“`java

0 赞同 0 条回复

八点上线永久会员 2023年9月7日下午5:29

递归方法

class Solution {
    ListNode left;
    public boolean isPalindrome(ListNode head) {
        left = head;
        return traverse(head);



    }
    public boolean traverse(ListNode right){
        if(right == null){
            return true;
        }
        boolean res =  traverse(right.next)&& (left.val == right.val) ;
        left = left.next;
        return res;
    }
}

“`java
“`

0 赞同 0 条回复

泡芙永久会员 2023年9月4日下午4:16

递归
– Time：O(n)
– Space：O(n)

class Solution {
    ListNode left;
    public boolean isPalindrome(ListNode head) {
        left = head;
        return traverse(head);
    }

    boolean traverse(ListNode right) {
        // 递归终止条件
        if (right == null) {
            return true;
        }
        // 关系式
        boolean res = traverse(right.next);
        res = res && (right.val == left.val);//回溯,从后往前
        left = left.next;//从前往后
        return res;
    }
}

快慢指针+反转链表

Time：O(n)
Space：O(1)

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 链表为空
        if (head == null || head.next == null) {
            return true;
        }

        // 1. 快慢指针找中点 slow
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 奇数需要slow再走一步才到回文段
        if (fast != null) {
            slow = slow.next;
        }

        // 2. 反转链表
        ListNode left = head;
        ListNode right = reverse(slow);
        while (right != null) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }

    ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

}

0 赞同 0 条回复

AD钙奶普通 2023年8月31日上午12:02

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null)  return true;
        // 找到中间节点
        ListNode tmp = findMid(head);
        // 反转链表
        ListNode a = reverseList(tmp.next);
        // 比较
        while(head != null && a != null) {
            if(head.val != a.val) {
                return false;
            }
            head = head.next;
            a = a.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        while(cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    public ListNode findMid(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

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

        return slow;
    }
}

0 赞同 0 条回复

Thaddeus 永久会员 2023年8月30日下午3:56

打卡

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return true;

        ListNode* HalfNode = middleFirstNode(head);
        ListNode* SecondHalfStart = reverseList(HalfNode->next);
        ListNode* curA = head;
        ListNode* curB = SecondHalfStart;
        while(curB != nullptr) {
            if(curA->val != curB->val) {
                return false;
            }
            curA = curA->next;
            curB = curB->next;
        }
        HalfNode->next = reverseList(SecondHalfStart);
        return true;

    }

    //找到链表的第一个中间结点
    ListNode* middleFirstNode(ListNode* head){
        if(head == nullptr || head->next == nullptr) return head;

        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }

    //翻转链表
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        while(cur != nullptr) {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
};

0 赞同 0 条回复

阿尚普通 2023年8月17日上午11:53

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null) return false;
        if(head.next == null) return true;

        //找链表的中点
        ListNode p1 = head;
        ListNode p2 = head;
        while(p1.next != null && p1.next.next != null){
            p1 = p1.next.next;
            p2 = p2.next;
        }

        //分割链表
        ListNode headB = p2.next;
        p2.next = null;

        //反转后面的链表
        headB = reverse(headB);


        p1 = head;
        p2 = headB;
        while(p2 != null){
            if(p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }

    public ListNode reverse(ListNode head){
        if(head == null) return null;

        ListNode pre = null;
        ListNode nxt = null;

        while(head != null){
            nxt = head.next;

            head.next = pre;
            pre = head;

            head = nxt;
        }

        return pre;
    }
}

0 赞同 0 条回复

纸飞机永久会员 2023年8月9日上午2:16

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        //找中间节点，偶数长度取左边
        ListNode *first = head;
        ListNode* last = get_middle_node(head)->next;
        last = reserve(last);
        while(last)
        {
            if(first->val != last->val)
            {
                return false;
            }
            first = first ->next;
            last = last ->next;
        }
        return true;
    }
    ListNode* get_middle_node(ListNode* head)
    {
        if(head &&　!head->next)
        {
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast->next && fast->next->next)
        {

            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
    ListNode* reserve(ListNode*head)
    {
        if(!head)
            return nullptr;
        if(head && !head->next)
            return head;
        ListNode* new_head = reserve(head->next);
        head->next->next = head;
        head->next = nullptr;
        return new_head;
    }
};

0 赞同 0 条回复

𬍤永久会员 2023年7月28日下午5:16

O(n)，O(n)

class Solution {
    public boolean isPalindrome(ListNode head) {
        List<Integer> vals = new ArrayList<Integer>();

        //复制
        ListNode node = head;
        while(node != null){
            vals.add(node.val);
            node = node.next;
        }

        //判断
        int slow = 0;
        int fast = vals.size() - 1;
        while(slow < fast){
            if(!vals.get(slow).equals(vals.get(fast))){
                return false;
            }
            slow++;
            fast--;
        }
        return true;

    }
}

0 赞同 0 条回复

Mr.肖永久会员 2023年7月7日上午11:33

打卡

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head.next == null || head == null)
            return true;

        ListNode cur = head;
        int n = 1;
        while(cur.next != null){
            cur = cur.next;
            n++;
        }

        //找到链表中靠由的中间节点
        int rindex = (n/2)+1;

        cur = head;
        n=1;
        while(n != rindex){
            cur = cur.next;
            n++;
        }
        //反转后半部分链表
        ListNode newNode = reverse(cur);

        ListNode a = head;
        while(newNode != null){
            if(a.val != newNode.val)
                return false;
            a = a.next;
            newNode = newNode.next;
        }
        return true;


    }
    private static ListNode reverse(ListNode head){
        if(head == null || head.next == null)
            return head;
        ListNode newNode;
        newNode = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newNode;
    }
}

0 赞同 0 条回复

Zn_XiangR 永久会员 2023年6月20日上午10:05

提交

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    let fast = head, slow = head
    while (fast !== null && fast.next !== null && fast.next.next !== null) {
        fast = fast.next.next
        slow = slow.next
    }
    let reverseHead = reverseLink(slow.next)
    while (reverseHead !== null) {
        if (reverseHead.val !== head.val) {
            return false
        }
        reverseHead = reverseHead.next
        head = head.next
    }
    return true
};
const reverseLink = function(head) {
    if (head === null || head.next === null) {
        return head
    }
    let headReverse = reverseLink(head.next)
    head.next.next = head
    head.next = null
    return headReverse
}

0 赞同 0 条回复

KEV 永久会员 2023年6月15日下午1:14

class Solution {
    ListNode* frontPointer; //保存前向结点，用于在递归中进行比较
public:
    bool recursivelyCheck(ListNode* currentNode) {
        if(currentNode==nullptr){
            return true;
        }
        bool bo=recursivelyCheck(currentNode->next);
        if(bo && currentNode->val == frontPointer->val){
            frontPointer=frontPointer->next;
            return true;
        }
        return false;
    }

    bool isPalindrome(ListNode* head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
};

0 赞同 0 条回复

Violet 永久会员 2023年5月9日下午5:02

时间复杂度：O（n）,空间复杂度O（n）

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.next == null) {
            return true;
        }
        ListNode temp = head;
        int len = 0;
        while (temp != null) {
            temp = temp.next;
            len++;
        }
        temp = head;
        for (int i = 0; i < len / 2 - 1; i++) {
            temp = temp.next;
        }
        ListNode newhead = reverse(temp.next);
        ListNode left = head, right = newhead;
        int i = 0;
        while (i++ < len / 2) {
            if (left.val != right.val) {
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;

    }
    ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newhead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newhead;
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年4月27日下午6:10

//时间复杂度O(n)，空间复杂度O(n)
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode ans = new ListNode();
        ListNode p = head;
        while(p != null)
        {
            ListNode q = new ListNode(p.val);
            q.next = ans.next;
            ans.next = q;
            p = p.next;
        }
        p = head;
        ListNode q = ans.next;
        while(p != null)
        {
            if(p.val != q.val)
                return false;
            else
            {
                p = p.next;
                q = q.next;
            }
        }
        return true;
    }
}

0 赞同 0 条回复

小趴菜永久会员 2023年4月23日下午8:20

时间o(n),空间o（1）;
class Solution {
public boolean isPalindrome(ListNode head) {
//判断一下特殊情况吧，给一个数或者空链表时
if(head null||head.nextnull){
return true;
}
ListNode fast,slow;
slow = fast = head;
//循环使得fast在null停下（偶数会停在null处，但是奇数会停在上一步）
while(fast !=null&&fast.next !=null){
slow = slow.next;
fast = fast.next.next;
}
//如果奇数则调整一下slow使其指向右半第一个
if(fast!=null){
slow = slow.next;
}
//开始翻转slow后的链表用两个指针往中间靠近比对
ListNode left = head;
ListNode right = reverse(slow);
//比对细节即停止循环条件
while(right!=null){
if(left.val!=right.val){
return false;
}
left = left.next;
right = right.next;
}
return true;
}
ListNode reverse(ListNode head){
if(headnull||head.nextnull){
return head;
}
ListNode newNode = reverse(head.next);
head.next.next = head;
head.next = null;
return newNode;
}
}

0 赞同 0 条回复

Only You!(^-^(^-^)) 永久会员 2023年4月20日下午8:39

//思路：
    //1.先找到中间节点靠后的
    //2.反转后半部分
    //3.判断回文
    //4.恢复链表，即再次反转后半部分链表
    //5.返回结果
    public boolean isPalindrome(ListNode head) {
        if (head == null) return true;
        boolean ans = true;
        //返回中间节点后面的那个
        ListNode mid = middleNode(head);
        //反转后半部分链表
        ListNode tail = reverseList(mid);
        //判断回文
        ListNode t1 = head;
        ListNode t2 = tail;
        while (t2 != null){
            if (t1.val != t2.val) ans = false;
            t1 = t1.next;
            t2 = t2.next;
        }

        //还原链表并返回结果
        //在对后半部分进行翻转即可恢复
        reverseList(tail);
        return ans;

    }

    ListNode middleNode(ListNode head) {
        if (head == null) return null;
        ListNode slow = head, fast = head;
        while (fast!= null && fast.next!= null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode t = curr.next;
            curr.next = prev;
            prev = curr;
            curr = t;
        }
        return prev;
    }

0 赞同 0 条回复

庄重普通 2023年4月20日下午8:31

class Solution {
public:
    bool isPalindrome(ListNode* head) {

        // 判断特殊情况
        if(head == nullptr || head->next == nullptr) return true;
        // 找到中间节点，偶数返回中间的第二个节点, 后面的节点数量 <= 前面的节点数量
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast != nullptr && fast->next != nullptr) {

            fast = fast->next->next;
            slow = slow->next;
        }
        // 反转并比较
        ListNode *p = reverse(slow);
        while(p != nullptr) {

            if(p->val != head->val) {
                return false;
            }
            p = p->next;
            head = head->next;
        }
        return true;
    }
    ListNode* reverse(ListNode *head) {

        ListNode *pCur = head;
        ListNode *pPre = nullptr;
        ListNode *pTmp = nullptr;
        while(pCur != nullptr) {

            pTmp = pCur->next;
            pCur->next = pPre;
            pPre = pCur;
            pCur = pTmp;
        }
        return pPre;
    }
};
// 时间复杂度O(2n);
// 空间复杂度O(1);

0 赞同 0 条回复

小肸永久会员 2023年4月18日下午7:11

找到中点slow(偶数个链表节点返回中间第一个节点)。

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        ListNode slow = head, fast = head.next;
        ListNode pre = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            ListNode temp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = temp;
        }
        if (fast != null) {//fast!=null说明链表节点数是偶数，需要多进行一次反转操作
            ListNode temp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = temp;
        }  else {//fast==null说明链表节点为奇数，中间节点的next指针不用反转，让slow=slow.next忽略中间节点的判断操作
            slow = slow.next;
        }
        while (pre != null && slow != null && pre.val == slow.val) {
            pre = pre.next;
            slow = slow.next;
        }
        return pre == null && slow == null;
    }

0 赞同 0 条回复

C++小将永久会员 2023年4月17日下午9:33

打卡

时间：O(n),空间O(1)

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head->next) return true;
        ListNode *slow = head, *fast = head;
        while(fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *newNode = reverseList(slow->next);
        slow->next = nullptr;

        while(head && newNode) {
            if(head->val != newNode->val) return false;
            head = head->next;
            newNode = newNode->next;
        }
        return true;
    }
    ListNode *reverseList(ListNode *head) {
        if(!head || !head->next) {
            return head;
        }
        ListNode *pre = nullptr;
        ListNode *cur = head;
        ListNode *temp = nullptr;
        while(cur) {
            temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    } 
    // ListNode *reverseList(ListNode *head) {
    //     if(!head || !head->next) {
    //         return head;
    //     }
    //     ListNode *res = reverseList(head->next);
    //     head->next->next = head;
    //     head->next = nullptr;
    //     return res;
    // }
};

0 赞同 0 条回复

秊永久会员 2023年4月17日上午10:25

时间：$O(n)$
空间：$O(1)$

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (null == head.next) return true;
        ListNode pre = head, last = head;
        int length = 2;

        // 得到链表的长度
        while (null != last.next.next) {
            last = last.next;
            ++length;
        }

        // 找到中间节点
        length = (length + 1) / 2;
        last = head;
        while (0 != length--) {
            last = last.next;
        }

        // 将后半段链表反转
        ListNode headNew = reverse(last);

        // 一一比较
        while (null != headNew) {
            if (pre.val != headNew.val) {
                return false;
            } else {
                pre = pre.next;
                headNew = headNew.next;
            }
        }

        return true;
    }

    // 反转链表
    public ListNode reverse(ListNode head) {
        ListNode last = null, pre = head;

        while (pre != null) {
            ListNode tmp = pre.next;
            pre.next = last;
            last = pre;
            pre = tmp;
        }

        return last;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2023年4月16日下午7:27

时间O(n)
空间O(1)

class Solution {
    public boolean isPalindrome(ListNode head) {
        //  O(n)的空间复杂度：存入数组去判断
        //O(1) 快指针找到后半部分，反转后半部分，判断是否回文
        if (head == null) {
            return true;
        }
        ListNode fast = head;
        ListNode slow = head;
        //遍历找到链表的尾部
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        //反转
        ListNode end = reverse(slow);
        //判断是否回文
        boolean res = ret(head,end);
        return res;
    }
    public ListNode reverse(ListNode head){
        ListNode temp = head;
        ListNode he = null;
        while(temp != null){
            ListNode next = temp.next;
            temp.next = he;
            he = temp;
            temp = next;
        }
        return he;
    }
    public boolean ret(ListNode left,ListNode right){
        while( left != null && right!= null){
            if(left.val != right.val){
                return false;
            }
            left = left.next;
            right = right.next;
        }
        return true;
    }
}

0 赞同 0 条回复

Everglow 永久会员 2023年4月16日下午1:37

时间O(n),空间O(1)

class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) {
            return true;
        }
        ListNode slow = head;
        ListNode fast = head;
        // 找到回文的中间结点或者第一组的最后一个结点
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 反转回文中的第二组
        // 1->2->2->1 => 1->2->2<-1
        slow = reverse(slow.next);
        //遍历两组链表 
        while(slow != null) {
            if(head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode curr = head;
        while(curr != null) {
            ListNode nextNode = curr.next;
            curr.next = pre;
            pre = curr;
            curr = nextNode;
        }
        return pre;
    }
}

0 赞同 0 条回复

【作业6_2】链表专题：回文链表

共以下 21 个回答

打卡

打卡

# 回答此问题取消回复

【作业6_2】链表专题：回文链表

共以下 21 个回答

打卡

打卡

# 回答此问题 取消回复

# 回答此问题取消回复