c - 在单个遍历链表中交换从开始到结束的第 k 个位置

Question

我遇到了以下实现，用于在单次遍历中交换链表中从开始到结束的第 k 个位置。

node *list;
node *p, *q, *r;
p = q = r = list;

i = 1;

while(p != NULL)
{
    if(i != k)
    {
        q = q->next;
        i++;
    }//q will eventually point to kth node from starting

    if(i == k)
    {
        r = r->next
    }//r will eventually point to kth node from end

    p = p->next;

}

 Swap q & r elements

但我觉得这不是正确的实现方式，谁能看一下并验证它是否正确？

如果错了，我必须做出哪些改变？

Answer 1

这个问题主要与找到正确的节点和相应的前一个节点有关。那么基本上有两种情况，节点是起始节点和结束节点，或者它们是中间节点。

先调整previous指针指向交换目标，然后交换targets的next指针。就这些了……下面是完整的java代码供引用->

JAVA代码

public class SwapKthNodeTest {

    public static void main(String[] args) {

        Test10Node();
        System.out.println();
        Test2Node();
    }

    private static void Test2Node() {
        Node head = Node.getNodeListHead(2);
        Node.ToString(head);
        int k = 1;
        head = Node.SwapKthNodeFromStartNEnd(head, k);
        Node.ToString(head);
        k = 2;
        head = Node.SwapKthNodeFromStartNEnd(head, k);
        Node.ToString(head);
    }

    public static void Test10Node(){
        Node head = Node.getNodeListHead(10);
        Node.ToString(head);
        int k = 2;
        head = Node.SwapKthNodeFromStartNEnd(head, k);
        Node.ToString(head);
        k=1;
        head = Node.SwapKthNodeFromStartNEnd(head, k);
        Node.ToString(head);
        k=3;
        head = Node.SwapKthNodeFromStartNEnd(head, k);
        Node.ToString(head);
        k=4;
        head = Node.SwapKthNodeFromStartNEnd(head, k);
        Node.ToString(head);
        k=5;
        head = Node.SwapKthNodeFromStartNEnd(head, k);
        Node.ToString(head);

    }

}

class Node {
    int val;
    Node next;
    Node(int val, Node next) {
        this.val = val;
        this.next= next;
    }
    public static int length(Node head){
        Node trav = head;
        int count = 0;
        while(trav != null){
            count++;
            trav = trav.next;
        }
        return count;
    }
    public static void ToString(Node head) {
        // just print the list which we created
        Node trav = head;
        while(trav != null){
            System.out.print(trav.val+" ");
            trav = trav.next;
        }
    }

    public static Node SwapKthNodeFromStartNEnd(Node head, int k) {
        System.out.println();

        int len = Node.length(head);
        if( k > len)    return head;

        // would be the same thing just making it reverse
        // to make process more cleaner
        if( k == len)   k = 1;

        Node x = head, y = head, t = head;
        Node xp = null, yp = null;
        int i = 1;

        while (i++ < k) {
            xp = x;
            x  = x.next;
            t  = t.next;
        }

        while(t.next != null){
            yp = y;
            y  = y.next;
            t  = t.next;
        }

//      System.out.println("x= "+x.val+" y= "+ y.val);
//      if(xp != null)  System.out.println("xp= "+xp.val);
//      if(yp != null)  System.out.println("yp= "+yp.val);

        // first adjust previous pointer of two nodes
        // later swap the next pointers of both nodes

        // CASE-1: case nodes have previous pointer
        // and they are not start and end node 
        if(xp != null && yp != null ){
            xp.next = y;
            yp.next = x;
        }
        // CASE-2: x and y nodes are first and last
        // this case xp is null
        else if (xp == null && yp != null){
            head    = y;
            yp.next = x;
        }

        t      = y.next;
        y.next = x.next;
        x.next = t;

        return head;
    }


    public static Node getNodeListHead(int nodes){
        int idx = nodes-1;
        Node head = new Node(nodes, null);
        while(idx >= 1){
            head = new Node(idx, head);
            idx--;
        }


        return head;
    }
}