[LintCode] Swap Two Nodes in Linked List

wua_wua2012 發(fā)布于2019-08-14 14:41 / 1468人閱讀

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

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

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65154.html

[LintCode] Swap Nodes in Pairs

摘要：指針為，我們選擇的兩個結(jié)點是和。要注意循環(huán)的邊界條件，這兩個結(jié)點不能為空。主要思路是先用和兩個新結(jié)點去保存和兩個結(jié)點。完成交換之后，連接和，并讓前進至此時的結(jié)點。 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-

摘要：三指針法復雜度時間空間思路基本的操作鏈表，見注釋。注意使用頭節(jié)點方便操作頭節(jié)點。翻轉(zhuǎn)后，開頭節(jié)點就成了最后一個節(jié)點。 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

摘要：新建兩個鏈表，分別存和的結(jié)點。令頭結(jié)點分別叫作和，對應的指針分別叫作和。然后遍歷，當小于的時候放入，否則放入。最后，讓較小值鏈表尾結(jié)點指向較大值鏈表頭結(jié)點，再讓較大值鏈表尾結(jié)點指向。 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