Electrical stimulation of shape-memory polymers (SMPs) has many advantages over thermal methods; creating an efficient conductive path through the bulk polymers is essential for developing high performance electroactive systems. Here, we show that a three-dimensional (3D) porous carbon nanotube sponge can serve as a built-in integral conductive network to provide internal, homogeneous, in situ Joule heating for shape-memory polymers, thus significantly improving the mechanical and thermal behavior of SMPs. As a result, the 3D nanocomposites show a fast response and produce large exerting forces (with a maximum flexural stress of 14.6 MPa) during shape recovery. We further studied the construction of a double-layer composite structure for bidirectional actuation, in which the shape change is dominated by the temperature-dependent exerting force from the top and bottom layer, alternately. An inchworm-type robot is demonstrated whose locomotion is realized by such bidirectional shape memory. Our large stroke shape-memory nanocomposites have promising applications in many areas including artificial muscles and bionic robots.