Przekroczony limit czasu w zadaniu z polindromami na liście kierunkowej

Chodzi o to zadanie: https://leetcode.com/problems/palindrome-linked-list/

Oto moje rozwiązanie:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        int size = 0;
        ListNode tmp = head;
        
        boolean isP = true;

        while (tmp != null)
        {
            size++;
            tmp = tmp.next;
        }
        
        int start = 0;
        int end = size - 1;

        while (start < end)
        {
            ListNode first = head;
            ListNode last = head;

            for (int i = 0 ; i < start ; i++)
            {
             first = first.next;
            }

            for (int i = 0 ; i < end ; i++)
            {
             last = last.next;
            }


            if (first.val != last.val)
            {
                isP = false;
                break;
            }
            else
            {
                start++;
                end--;
            }

        }
           return isP;
    }
}

Czy jestem w stanie jakoś zmodyfikować ten kod bez zmieniania logiki aby uniknąć time limitu?

Nie, problem jest w logice, za bardzo pętlisz :P

Próbowałeś odwrócić listę i wtedy lecieć z porównaniem od początku?

edit. albo lepiej (ale nie wiem czy można z innych struktur korzystać na leetcode bo nigdy tego nie używałem) - wrzuć to do arraylisty i jedziesz od początku i od końca getem

Nie da się poprawić tego "kodu", tak żeby był w stanie przeanalizować 100 000 pozycji. Masz "główny" przebieg po liście n elementów, w każdym z tych przebiegów odpalasz 2 pętle, które mają ci znaleźć żądane elementy. Tak na szybko to jesteś w okolicach O((n/2)!) a 50000! to nadal bardzo dużo :D

Ja się przejąłem tym O(n) i M(1). Wyszło coś takiego (liczenia hasha zrobiłem baaaaaardzo na odwal się, ale przeszedł). Nie wiem czy jest szybko, bo zapomniałem wywalić println() przed oddaniem, Nadal wykonuje się poniżej 2 sekund. Złożoność pamięciowa w czołówce, pomimo tego babola.

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun isPalindrome(head: ListNode?): Boolean {
        val length = listLength(head!!)
        
        var node = head
        var index = 0
        var steppingSum = 0
        var alternateSum = 0

        while(node != null){
            val multiplier = closestEdgeIndex(index, length) + 11
            val hash = (multiplier * (node.`val` + 13)) * (multiplier % 3 * node.`val` +1) * (multiplier % 5 * node.`val` +1)
            
            if((length-1) > index * 2){
                steppingSum += hash
            } 
            if((length-1) < index * 2) { //intentionally skipped middle element
                steppingSum -= hash
            }
            index++
            node = node.next
        }

        return steppingSum == 0
    }

    fun closestEdgeIndex(index:Int, length: Int): Int {
        val backwardIndex = length - index -1
        return if(backwardIndex < index){
            backwardIndex
        } else {
                index
                }
    }

    fun listLength(head: ListNode?): Int{
        var counter = 0
        var node = head
        while (node != null){
            counter++
            node = node.next
        }
        return counter
    }
}

No dobra, za fajnie wyszło, żeby się nie pochwalić

piotrpo napisał(a):

Tak na szybko to jesteś w okolicach O((n/2)!) a 50000! to nadal bardzo dużo :D

Nie, O(N*N) pętla po start/stop iterująca z obu stron naraz (N/2) wewnątrz pętli 0..start i 0..end sumujące się do (start+end) czyli (N).

Algorytm:

1. Mierzysz długość listy.
2. Odwracasz w miejscu do połowy
3. Ewentualnie pomijasz środkowy element
4. Porównujesz odwróconą pierwszą połowę z drugą połową
5. Ewentualnie odtwarzasz listę odwracając w miejscu.

Podam rozwiązanie w C++

#include <iostream>
using namespace std;

class ListNode
{
	public:
	int val;
	ListNode *next;
	ListNode() {}
    ListNode(int val,ListNode *next=nullptr):val(val),next(next) {}
};

size_t CountNodes(ListNode *node)
{
	size_t count=0;
	for(;node;++count) node=node->next;
	return count;
}

void MoveNode(ListNode **dst,ListNode **src)
{
	ListNode *tmp=*src;
	*src=tmp->next;
	tmp->next=*dst;
	*dst=tmp;
}

void show(ListNode *node)
{
	cout<<"{ ";
	for(;node;node=node->next) cout<<node->val<<' ';
	cout<<'}'<<endl;
}

bool isPalindrome(ListNode *head)
{
	size_t count=CountNodes(head);
	ListNode *rev=nullptr;
	for(size_t half=count>>1;half--;) MoveNode(&rev,&head);
	bool ok=true;
	for(ListNode *a=(count&1?head->next:head),*b=rev;(b)&&(ok);a=a->next,b=b->next) if(a->val!=b->val) break;
	for(size_t half=count>>1;half--;) MoveNode(&head,&rev);	// Jeżeli musimy odtworzyć
	return ok;
}


int main()
{
	ListNode tst[5]
	{
		ListNode(1,tst+1),
		ListNode(2,tst+2),
		ListNode(3,tst+3),
		ListNode(2,tst+4),
		ListNode(1,nullptr),
	};
	show(tst);
	cout<<(isPalindrome(tst)?"Yes":"No")<<endl;
	show(tst);
	return 0;
}

Koszt O(N)