Swap two nodes in a singly linked list

Question

How to switch two nodes in a singly linked list in pascal?

procedure List.switch(var n1,n2 : pNode);
var aux : pNode;
begin
  aux := n1;
  p1:= n2;
  n2 := aux;
end;

(Here pNode is a pointer on a node in the list.)

Nodes are defined like this:

pNode = ^Node;
Node = record
    data : data;
    next : pNode;
end;

This code doesn't work. It either doesn't compile, saying "Can't take the address of constant expressions", or just doesn't do anything. I guess it has to do with how pointers work...

I found relevant information here, but I don't read C.

Thanks for any advice!

Answer 1

Something like this should work for you. It uses a local variable of type Node (which is presumably what PNode is a pointer to) as a placeholder.

procedure List.Switch(NodeA, NodeB: PNode);
var
  Temp: Node;
begin
  Temp.Data := NodeB^.Data;
  Temp.Next := NodeB^.Next;
  NodeB^.Data := NodeA^.Data;
  NodeB^.Next := NodeA^.Next;
  NodeA^.Data := Temp.Data;
  NodeA^.Next := Temp.Next;
end;

Here's a version of it that isn't an object method, with a console app that tests it:

program Project1;

uses
  System.SysUtils;

type
  PNode = ^Node;
  Node = record
    Data: Integer;
    Next: PNode;
  end;

procedure Swap(NodeA, NodeB: PNode);
var
  Temp: Node;
begin
  Temp.Data := NodeB^.Data;
  Temp.Next := NodeB^.Next;
  NodeB^.Data := NodeA^.Data;
  NodeB^.Next := NodeA^.Next;
  NodeA^.Data := Temp.Data;
  NodeA^.Next := Temp.Next;
end;

var
  A, B: Node;
  pA, pB: PNode;

begin
  New(pA);
  pA^.Data := 1;
  pA^.Next := nil;
  New(pB);
  pB^.Data := 2;
  pB^.Next := @A;
  WriteLn('Before - pA^.Data: ', pA^.Data, ' pB^.Data: ', pB^.Data);
  Swap(pA, pB);
  WriteLn('After - pA^.Data: ', pA^.Data, ' pB^.Data: ', pB^.Data);    // Outputs 2 and 1
  Readln;
  Dispose(pA);
  Dispose(pB);
end.

Answer 2

I think something like this would work:

function SwapNodes(first: pNode): pNode;
begin
  Result := first.next;
  first.next := Result.next;
  Result.next := first;
end;