Можно ли использовать очереди для обмена соседними узлами связанного списка? - PullRequest
Новая
       90

Можно ли использовать очереди для обмена соседними узлами связанного списка?

0 голосов
/ 01 августа 2020

Я пытался поменять местами соседние узлы связанного списка, используя очереди. Ниже приведен код: 

class Solution {
    public ListNode swapPairs(ListNode head) {
        Queue<ListNode> q1 = new LinkedList<>();
        Queue<ListNode> q2 = new LinkedList<>();
        ListNode curr = head;
     
        while(curr != null && curr.next != null){
            q1.offer(curr);
            curr = curr.next.next;
        }
        curr = head.next;
        while(curr != null || !q1.isEmpty()){
            if(curr != null)
            q2.offer(curr);
            
            q2.offer(q1.poll());  //this line seems to be the problem
            
            if(curr.next != null)
            curr = curr.next.next;
            else
                curr = curr.next;
        }
        ListNode dummy = new ListNode(0);
        curr = dummy;
        while(!q2.isEmpty()){
            dummy.next = q2.poll();
            dummy = dummy.next;
        }
        return curr.next;
    }
}

Я пробовал это, но получил сообщение об ошибке: Найден цикл в ListNode. Пожалуйста помоги. Когда я попробовал отладку, я обнаружил, что q2.offer(q1.poll());, похоже, вызывает проблему.

PS Я знаю, что есть более простой способ решить этот вопрос, а именно, одна итерация и использование указателей . Но я немного новичок в программировании. Итак, я пробую что-то, но не могу понять, почему приведенный выше код выдает ошибку.

1 Ответ

0 голосов
/ 02 августа 2020

Внесены некоторые изменения в ваш код. Обнаружена проблема при построении списка обратно из очереди. 

public ListNode swapPairs(ListNode head) {
            Queue<ListNode> q1 = new LinkedList<>();
            Queue<ListNode> q2 = new LinkedList<>();
            ListNode curr = head;
         
            while(curr != null && curr.next != null){
                q1.offer(curr);
                curr = curr.next.next;
            }
           
           // If there are odd numbers in the list
            if (curr!=null)
                q1.offer(curr);
            
            curr = head.next;
            while(curr != null || !q1.isEmpty()){
                if(curr != null) {
                    System.out.println(curr.val);
                    q2.offer(curr);
                }
                 
                q2.offer(q1.poll());  
                
                if (curr == null)
                    continue;
                
                if(curr.next != null)
                    curr = curr.next.next;
                else
                    curr = curr.next;
            }
            

            curr = q2.poll();
            head = curr;
            
            while(!q2.isEmpty()){

                // create a new node
                ListNode dummy = new ListNode(0);
                dummy.val = q2.poll().val;
                dummy.next = null;
                
                curr.next = dummy;
                curr = dummy;               
            }
            
            return head;
}

Input: 1 2 3 4 5 
Output: 2 1 4 3 5

Input: 1 2 3 4
Output: 2 1 4 3
...