<small id="eyigc"></small>

[LintCode] Swap Two Nodes in Linked List

wua_wua2012 發布于2019-08-14 14:41 / 1460人閱讀

摘要：建立結點，指向可能要對進行操作。找到值為和的結點設為，的前結點若和其中之一為，則和其中之一也一定為，返回頭結點即可。正式建立，，以及對應的結點，，然后先分析和是相鄰結點的兩種情況是的前結點，或是的前結點再分析非相鄰結點的一般情況。

Problem

Given a linked list and two values v1 and v2. Swap the two nodes in the linked list with values v1 and v2. It"s guaranteed there is no duplicate values in the linked list. If v1 or v2 does not exist in the given linked list, do nothing.

Notice

You should swap the two nodes with values v1 and v2. Do not directly swap the values of the two nodes.

Example

Given 1->2->3->4->null and v1 = 2, v2 = 4.

Return 1->4->3->2->null.

Note

建立dummy結點，指向head（可能要對head進行操作）。
找到值為v1和v2的結點（設為n1，n2）的前結點p1, p2；
若p1和p2其中之一為null，則n1和n2其中之一也一定為null，返回頭結點即可。
正式建立n1，n2，以及對應的next結點x1，x2，然后：
先分析n1和n2是相鄰結點的兩種情況：n1是n2的前結點，或n2是n1的前結點；
再分析非相鄰結點的一般情況。
返回dummy.next，結束。

Solution

public class Solution {
    public ListNode swapNodes(ListNode head, int v1, int v2) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p1 = null, p2 = null, cur = dummy;
        while (cur.next != null) {
            if (cur.next.val == v1) p1 = cur;
            else if (cur.next.val == v2) p2 = cur;
            cur = cur.next;
        }
        if (p1 == null || p2 == null) return dummy.next;
        ListNode n1 = p1.next, n2 = p2.next, x1 = n1.next, x2 = n2.next;
        if (p1.next == p2) {
            p1.next = n2;
            n2.next = n1;
            n1.next = x2;
        }
        else if (p2.next == p1) {
            p2.next = n1;
            n1.next = n2;
            n2.next = x1;
        }
        else {
            p1.next = n2;
            n2.next = x1;
            p2.next = n1;
            n1.next = x2;
        }
        return dummy.next;
    }
}

GPU云服務器云服務器 Nodes linked LintCode LintCode134_LRU

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65154.html

[LintCode] Swap Nodes in Pairs

摘要：指針為，我們選擇的兩個結點是和。要注意循環的邊界條件，這兩個結點不能為空。主要思路是先用和兩個新結點去保存和兩個結點。完成交換之后，連接和，并讓前進至此時的結點。 Problem Given a linked list, swap every two adjacent nodes and return its head. Example Given 1->2->3->4, you sh...

EscapedDog 2019-08-14 15:11 評論0 收藏0
[LeetCode/LintCode] Odd Even Linked List

Problem Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes. Example Example:Given...

awokezhou 2019-08-16 12:44 評論0 收藏0
[Leetcode] Swap Nodes in Pairs Reverse Nodes in k-

摘要：三指針法復雜度時間空間思路基本的操作鏈表，見注釋。注意使用頭節點方便操作頭節點。翻轉后，開頭節點就成了最后一個節點。 Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should ...

TZLLOG 2019-08-14 12:45 評論0 收藏0
[LintCode] Reverse Nodes in k-Group

Problem Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as ...

XGBCCC 2019-08-14 15:12 評論0 收藏0
[LintCode/LeetCode] Partition List

摘要：新建兩個鏈表，分別存和的結點。令頭結點分別叫作和，對應的指針分別叫作和。然后遍歷，當小于的時候放入，否則放入。最后，讓較小值鏈表尾結點指向較大值鏈表頭結點，再讓較大值鏈表尾結點指向。 Problem Given a linked list and a value x, partition it such that all nodes less than x come before no...

崔曉明 2019-08-14 16:26 評論0 收藏0