Add following custom functions in functions.php file and instead of calling previous_post_link and next_post_link functions call custom_next_post_link and custom_previous_post_link custom functions respectively.
function custom_adjacent_post_link( $format, $link, $in_same_cat = false, $excluded_categories="", $previous = true ) {
if ( $previous && is_attachment() )
$post = get_post( get_post()->post_parent );
else
$post = get_adjacent_post( $in_same_cat, $excluded_categories, $previous );
if ( ! $post ) {
$post="";
$args="posts_per_page=1&orderby=date&ignore_sticky_posts=1";
if($previous)
$args .= '&order=DESC';
else
$args .= '&order=ASC';
$the_query = new WP_Query( $args );
while ( $the_query->have_posts() ) :
$the_query->the_post();
$post = get_post(get_the_ID());
endwhile;
wp_reset_postdata();
}
$title = $post->post_title;
if ( empty( $post->post_title ) )
$title = $previous ? __( 'Previous Post' ) : __( 'Next Post' );
$title = apply_filters( 'the_title', $title, $post->ID );
$date = mysql2date( get_option( 'date_format' ), $post->post_date );
$rel = $previous ? 'prev' : 'next';
$string = '<a href="' . get_permalink( $post ) . '" rel="'.$rel.'">';
$inlink = str_replace( '%title', $title, $link );
$inlink = str_replace( '%date', $date, $inlink );
$inlink = $string . $inlink . '</a>';
$output = str_replace( '%link', $inlink, $format );
$adjacent = $previous ? 'previous' : 'next';
echo apply_filters( "{$adjacent}_post_link", $output, $format, $link, $post );
}
function custom_previous_post_link($format="« %link", $link='%title', $in_same_cat = false, $excluded_categories="") {
custom_adjacent_post_link($format, $link, $in_same_cat, $excluded_categories, true);
}
function custom_next_post_link($format="%link »", $link='%title', $in_same_cat = false, $excluded_categories="") {
custom_adjacent_post_link($format, $link, $in_same_cat, $excluded_categories, false);
}